RMQ问题是一类区间最值问题，这里给出一个特殊的RMQ问题，初始给定一个n长的排列P，注：n长排列是指有1~n这n个整数构成的一个序列每个整数恰好出现一次。并对这个排列P进行M次查询操作，每次查询形如Query（L，R），每次查询返回排列P中位置在区间[L,R]上所有数中最大的那个数，其中位置的下标从1开始。例如排列P = {3,1,4,2,5}，
那么Query(1,2) = max{3,1}=3,Query(2,4)=max{1,4,2}=4。由于RMQ问题对大家来说实在是太简单了，所以这题要求大家求解一个RMQ的逆问题，即给你排列的长度n，以及M次查询的问题及其结果三元组（Li,Ri,Qi），即Query（Li，Ri）=Qi，询问符合这M次查询的n长排列是否存在。若存在输出“Possible”；否则输出“Impossible”。
Input
多组测试数据，第一行一个整数T，表示测试数据数量，1<=T<=5
之后有T组结构相同的数据：
每组数据的第一行有两个整数n与M，其中1<=n<=10^9(即1,000,000,000)，1<=M<=50
之后会有M行，每行表示一个三元组Li,Ri,Qi,其中1<=Li<=Ri<=n,1<=Qi<=n
Output
每组数据输出一行，即“Possible”或“Impossible”不含引号
对于一个询问(L,R,Q)，能得到的信息是(Q,n]中的数只能在[1,L)或(R,n]，Q只能在[L,R]
因此离散化之后可以转化为最大流，左边的点代表每个数值/数值区间，右边的点代表每个区间，之间连边inf代表此数值可以在此区间内，源点到左边的点连边限制每个数值/数值区间中数值的个数，右边的点连边到汇点限制每个区间内数值的个数，当且仅当最大流为n时有解
#include<cstdio>
#include<algorithm>
const int N=,inf=0x3f3f3f3f;
int es[N],enx[N],ev[N],e0[N],ep;
int h[N],q[N],S,T;
inline void adde(int a,int b,int c){
es[ep]=b;enx[ep]=e0[a];ev[ep]=c;e0[a]=ep++;
es[ep]=a;enx[ep]=e0[b];ev[ep]=;e0[b]=ep++;
}
bool bfs(){
int ql=,qr=;
for(int i=;i<=T;i++)h[i]=;
h[S]=;q[qr++]=S;
while(ql!=qr){
int w=q[ql++];
for(int i=e0[w];i;i=enx[i]){
int u=es[i];
if(!h[u]&&ev[i]){
h[u]=h[w]+;
q[qr++]=u;
}
}
}
return h[T];
}
int dfs(int w,int f){
if(w==T)return f;
int c,u,used=;
for(int i=e0[w];i;i=enx[i]){
u=es[i];
if(h[u]!=h[w]+||!ev[i])continue;
c=f-used;
if(c>ev[i])c=ev[i];
c=dfs(u,c);
used+=c;
ev[i]-=c;
ev[i^]+=c;
if(used==f)return f;
}
if(!used)h[w]=;
return used;
}
int qs[][],xs[],ps[],xp,pp;
bool d[][];
int main(){
int _T,n,q;
for(scanf("%d",&_T);_T;_T--){
scanf("%d%d",&n,&q);
for(int i=;i<q;i++)scanf("%d%d%d",qs[i],qs[i]+,qs[i]+);
xp=pp=;
xs[xp++]=;
xs[xp++]=n+;
ps[pp++]=;
ps[pp++]=n+;
for(int i=;i<q;i++){
xs[xp++]=qs[i][];
xs[xp++]=qs[i][]+;
ps[pp++]=qs[i][];
ps[pp++]=qs[i][]+;
}
std::sort(xs,xs+xp);
xp=std::unique(xs,xs+xp)-xs;
std::sort(ps,ps+pp);
pp=std::unique(ps,ps+pp)-ps;
for(int i=;i<xp;i++)for(int j=;j<pp;j++)d[i][j]=;
for(int i=;i<q;i++){
for(int j=;j<xp-;j++){
if(xs[j]>qs[i][]){
for(int k=;k<pp-;k++)if(qs[i][]<=ps[k]&&ps[k]<=qs[i][]){
d[j][k]=;
}
}else if(xs[j]==qs[i][]){
for(int k=;k<pp-;k++)if(qs[i][]>ps[k]||ps[k]>qs[i][]){
d[j][k]=;
}
}
}
}
S=xp+pp+;T=S+;
for(int i=;i<=T;i++)e0[i]=;
ep=;
for(int i=;i<xp-;i++)adde(S,i+,xs[i+]-xs[i]);
for(int i=;i<pp-;i++)adde(xp+i+,T,ps[i+]-ps[i]);
for(int i=;i<xp-;i++)for(int j=;j<pp-;j++)if(d[i][j])adde(i+,xp+j+,n);
int ans=;
while(bfs())ans+=dfs(S,inf);
puts(ans==n?"Possible":"Impossible");
}
return ;
}