银河队选手名单出来了！小林，作为特聘的营养师，将负责银河队选手参加
宇宙比赛的饮食。众所周知，前往宇宙的某个星球，通常要花费好长好长的时间，人体情况在这之间会发生变化，因此，需要根据每天的情况搭配伙食，来保证营养。小林把人体需要的营养分成了n种，这些营养包括但不限于铁，钙。他准备了2套厨师机器人，一套厨师机器人有n个，每个厨师机器人只会做一道菜，这道菜一斤能提供第i种营养xi微克。想要吃这道菜的时候，只要输入一个数，就能吃到对应数量的这道菜了。为防止摄入过量对身体造成的伤害，每个机器人还有防过量摄入药，只要输入一个数，就能生成一定剂量的药，吃了这些药，就能减少相当于食用对应数目的这道菜提供的营养。
小林之所以准备2套厨师机器人，正是因为旅途漫漫，难以预计，也许某一个厨师机器人在途中坏掉，要是影响了银河队选手的身体，就不好了。因此，第2套厨师机器人被用来做第1套的备用。小林需要为每一个第1套厨师机器人选一个第2套厨师机器人作备份，使得当这个机器人坏掉时，用备份顶替，整套厨师机器人仍然能搭配出任何营养需求，而且，每个第2套厨师机器人只能当一个第1套厨师机器人的备份。

第一行包含一个正整数n。接下来n行，每行n个整数，表示第
1套厨师机器人做的菜每一斤提供的每种营养。再接下来n行，每行n个整数，表示第2套厨师机器人做的菜每一斤提供的每种营养。

第一行是一个字符串，如果无法完成任务，输出“NIE”，否则输
出“TAK”，并跟着n行，第i行表示第i个第1套机器人的备份是哪一个第2套机器人。为了避免麻烦，如果有多种可能的答案，请给出字典序最小的那一组。

对于100%的数据，1≤n≤300，所有出现的整数均非负，且不超过10,000。

  1 /*by SilverN*/  2 #include<iostream>  3 #include<algorithm>  4 #include<cstring>  5 #include<cstdio>  6 #define LL long long  7 using namespace std;  8 //const int mod=1e9+7;  9 const int mod=999911657; 10 const int mxn=303; 11 int read(){ 12     int x=0,f=1;char ch=getchar(); 13     while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 14     while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} 15     return x*f; 16 } 17 int n; 18 LL ksmul(LL a,LL b){ 19     int res=0; 20     while(b){ 21         if(b&1)res=((LL)res+a)%mod; 22         (a<<=1)%=mod; 23         b>>=1; 24     } 25     return res; 26 } 27 LL ksm(int a,int k){ 28     LL x=1; 29     while(k){ 30         if(k&1)x=ksmul(x,a); 31         a=ksmul(a,a); 32         k>>=1; 33     } 34     return x; 35 } 36 struct Mat{ 37     int x[mxn][mxn]; 38     Mat operator * (Mat b){ 39         Mat res; 40         for(int i=1;i<=n;i++){ 41             for(int j=1;j<=n;j++){ 42                 res.x[i][j]=0; 43                 for(int k=1;k<=n;k++) 44                     (res.x[i][j]+=(LL)x[i][k]*b.x[k][j]%mod)%=mod; 45             } 46         } 47         return res; 48     } 49     Mat Gauss_inv(){ 50         Mat inv; 51         int i,j,k; 52         for(i=1;i<=n;i++) 53             inv.x[i][i]=1;//初始化单位矩阵  54         for(i=1;i<=n;i++){ 55             if(!x[i][i]){ 56                 int p=i; 57                 for(j=i+1;j<=n;j++){ 58                     if(x[p][i]){p=i;break;} 59                 } 60                 for(j=1;j<=n;j++){ 61                     swap(x[p][j],x[i][j]); 62                     swap(inv.x[p][j],inv.x[i][j]); 63                 } 64             } 65             LL INV=ksm(x[i][i],mod-2); 66 //          printf("INV:%lld\n",INV); 67             for(j=1;j<=n;j++){ 68                 x[i][j]=x[i][j]*INV%mod; 69                 inv.x[i][j]=inv.x[i][j]*INV%mod; 70 //              printf("x%d %d:%d\n",i,j,inv.x[i][j]); 71             } 72             for(j=1;j<=n;j++){ 73                 if(j==i)continue; 74                 LL tmp=(mod-x[j][i])%mod; 75                 for(k=1;k<=n;k++){ 76                     (x[j][k]+=x[i][k]*tmp%mod)%=mod; 77                     (inv.x[j][k]+=inv.x[i][k]*tmp%mod)%=mod; 78                       79                 } 80             } 81         } 82         return inv; 83     } 84     void tran(){ 85         for(int i=1;i<=n;i++) 86             for(int j=i+1;j<=n;j++) 87                 swap(x[i][j],x[j][i]); 88         return; 89     } 90 }a,b,c; 91 void Debug(Mat a){ 92     printf("Debug\n"); 93     for(int i=1;i<=n;i++){ 94         for(int j=1;j<=n;j++){ 95             printf("%d ",a.x[i][j]); 96         } 97         printf("\n"); 98     } 99     printf("fin\n");100     return;101 }102 //Matrix103 int mp[mxn][mxn];104 int vis[mxn],Link[mxn];105 bool DFS(int u){106     for(int i=1;i<=n;i++)107         if(mp[u][i] && !vis[i]){108             vis[i]=1;109             if(!Link[i] || (DFS(Link[i])==1)){110                 Link[i]=u;111                 return 1;112             }113         }114     return 0;115 }116 bool Match(int u,int fa){117     for(int i=1;i<=n;i++)118         if(mp[u][i] && !vis[i]){119             vis[i]=1;120             if(Link[i]==fa || (Link[i]>fa && Match(Link[i],fa))){121                 Link[i]=u;122                 return 1;123             }124         }125     return 0;126 }127 //BP128 int ans[mxn];129 void Build(){130     int i,j;131     for(i=1;i<=n;i++)132         for(j=1;j<=n;j++)133             mp[i][j]=c.x[i][j]?1:0;134     for(i=1;i<=n;i++){135         memset(vis,0,sizeof vis);136         if(!DFS(i)){137             printf("NIE\n");138             return;139         }140     }141     printf("TAK\n");142     for(i=1;i<=n;i++){143         memset(vis,0,sizeof vis);144         Match(i,i);145     }146     for(i=1;i<=n;i++)ans[Link[i]]=i;147     for(i=1;i<=n;i++)printf("%d\n",ans[i]);148     return;149 }150 //151 int main(){152     int i,j;153     n=read();154     for(i=1;i<=n;i++)155         for(j=1;j<=n;j++)156             a.x[i][j]=read();157     for(i=1;i<=n;i++)158         for(j=1;j<=n;j++)159             b.x[i][j]=read();160 //  Debug(a);161     a=a.Gauss_inv();162     c=b*a;163 //  Debug(c);164     c.tran();165     Build();166     return 0;167 }