#include<bits/stdc++.h> #define ll long long #define inf 0x3f3f3f3f using namespace std; const int N=1e6+5; int n; ll a[N]; int lowbit(int x) { return x&(-x); } void add(int x) { for (int i=x;i<=n;i+=lowbit(i)) a[i]++; } ll sum(int x) { // cout<<x<<endl; ll s=0; for (int i=x;i>=1;i-=lowbit(i)) s+=a[i]; return s; } int main() { while(scanf("%d",&n)!=EOF) { n*=n; ll ans1=0,ans2=0; int x; memset(a,0,sizeof(a)); for (int i=1;i<=n;i++) { scanf("%d",&x); if (x) { ans1+=sum(n)-sum(x); add(x); } } memset(a,0,sizeof(a)); for (int i=1;i<=n;i++) { scanf("%d",&x); if (x) { ans2+=sum(n)-sum(x); add(x); } } if ((ans1%2)==(ans2%2)) printf("TAK\n"); else printf("NIE\n"); } return 0; }

• • 1. ~^^~