以下描述部分方向代指该方向的塔，建议画图理解
不妨假设左下的塔数\(\ge 2\)，这些塔覆盖区域构成阶梯形
考虑阶梯的交点，若其被左上/右下覆盖，则总可以去掉其中一个左下
换言之，这些交点均被右上覆盖，进而未覆盖区域构成两个\(\frac{1}{4}\)平面（左上和右下）
同时，由于左上/右下不允许覆盖阶梯交点，进而不会覆盖相对的未覆盖平面
此时，以左上的未覆盖平面为例，至多选一个右上缩小该平面，并用一个左上覆盖其余部分
综上，即得到了答案的结构（还有一种对称的情况，是同理的）
枚举左下最上的塔，那么对应右上仅需保证左边界合法（存在左上）并最小化下边界
以此类推，下一个左下即保证上边界合法并最大化右边界……，直至存在右下
另外，可能最初的右上是用来缩小平面的，那么可能额外选一个右上
显然处理第一步后，每次的状态仅由一个边界决定，进而仅有\(O(n)\)种，简单处理即可
时间复杂度为\(O(n)\)
#include<bits/stdc++.h>
using namespace std;
#define N 1000005
#define getc() ((p1==p2)&&(p2=(p1=buf)+fread(buf,1,500000,stdin),p1==p2) ? EOF : *p1++)
int t,n,ans,x[N],y[N],d[N],mny[N],Mxx[N],mxx[N],mxy[N],fx[N],fy[N];
static char buf[500001],*p1=buf,*p2=buf;
int read(){
int x=0;char c=getc();
while ((c<'0')||(c>'9'))c=getc();
while ((c>='0')&&(c<='9'))x=x*10+c-'0',c=getc();
return x;
}
int calc(){
for(int i=0;i<=n+1;i++)mny[i]=fx[i]=fy[i]=0x3f3f3f3f;
for(int i=0;i<=n+1;i++)Mxx[i]=mxx[i]=mxy[i]=0;
for(int i=1;i<=n;i++){
if (!d[i])mny[x[i]]=min(mny[x[i]],y[i]);
if (d[i]==1)Mxx[y[i]]=max(Mxx[y[i]],x[i]);
if (d[i]==2)mxx[y[i]]=max(mxx[y[i]],x[i]);
if (d[i]==3)mxy[x[i]]=max(mxy[x[i]],y[i]);
}
for(int i=2;i<=n;i++)mny[i]=min(mny[i-1],mny[i]);
for(int i=2;i<=n;i++)Mxx[i]=max(Mxx[i-1],Mxx[i]);
for(int i=n-1;i;i--)mxx[i]=max(mxx[i+1],mxx[i]);
for(int i=2;i<=n;i++)mxy[i]=max(mxy[i-1],mxy[i]);
for(int i=1;i<=n;i++)
if (d[i]==2){
int x0=x[i],y0=mny[min(x[i],Mxx[y[i]])];
if (y0>y[i])continue;
if (y0<=mxy[x0])return 4;
fx[x0]=min(fx[x0],3+(y0>mny[x0]));
fy[y0]=min(fy[y0],3+(x0<mxx[y0]));
}
int y=n,ans=0x3f3f3f3f;
for(int x=1;x<=n;x++){
while (y>mny[x]){
if (mxx[y])fx[mxx[y]]=min(fx[mxx[y]],fy[y]+(y>mny[mxx[y]]));
y--;
}
if (mny[x]!=0x3f3f3f3f)fy[mny[x]]=min(fy[mny[x]],fx[x]+(x<mxx[mny[x]]));
}
while (y){
if (mxx[y])fx[mxx[y]]=min(fx[mxx[y]],fy[y]+(y>mny[mxx[y]]));
y--;
}
for(int x=1;x<=n;x++)
if (mny[x]<=mxy[x])ans=min(ans,fx[x]+1);
for(int y=1;y<=n;y++)
if ((mxx[y])&&(y<=mxy[mxx[y]]))ans=min(ans,fy[y]+1);
return ans;
}
int main(){
t=read();
for(int I=1;I<=t;I++){
n=read();
for(int i=1;i<=n;i++)x[i]=read(),y[i]=read(),d[i]=read()-1;
ans=calc();
for(int i=1;i<=n;i++)y[i]=n-y[i]+1,d[i]^=3;
ans=min(ans,calc());
printf("Case #%d: ",I);
if (ans<=n)printf("%d\n",ans);
else printf("Impossible\n");
}
return 0;
}