1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
#include<bits/stdc++.h> 

typedef long long ll; 
using namespace std; 

void solve(){ 
    int n; cin >> n; 
    vector<int> v; 
    ll sum[2] = {0, 0};  
    ll sumall = 0;  
    int zeros_only = 1; 
    int read;  
    int cnt = 0; 
    for(int i = 0; i < n; i++){  
        cin >> read; 
        if(zeros_only && read == 0) 
            continue; 
        if(read > 0)  
            zeros_only = 0; 
        v.push_back(read); 
        sum[(cnt++)%2] += read; 
    } 
    while(v.size() > 1 && v.back() == 0) 
        v.pop_back(); 
    n = v.size();
    //cout << "SUMY: " << sum[0] << " " << sum[1] << "\n"; 
    if(n == 1 && v[0] > 1){ 
        cout << "NIE\n"; 
        return; 
    }
    sumall = sum[0] + sum[1]; 
    if(fabs(sum[0] - sum[1]) > 1){ 
        cout << "NIE\n"; 
        return; 
    }
    ll prefsum = 0; 
    for(int i = 0; i < n; i++){ 
        prefsum += v[i]; 
        if(prefsum > 0 && v[i] == 0 && prefsum != sumall){ 
            cout << "NIE\n"; 
            return ; 
        }
    } 
    if(n == 2){ 
        cout << "TAK\n"; 
        return; 
    }
    if(v[0] > 0 && v[1] > 0 && v[2] > 0 && v[0] > v[1]){
        cout << "NIE\n"; 
        return; 
    }
    if(v[n-1] > 0 && v[n-2] > 0 && v[n-3] > 0 && v[n-1] > v[n-2]){ 
        cout << "NIE\n"; 
        return; 
    } 
    // zliczanie koncow 
    bool forced = 0; int par; 
    if(sum[0] != sum[1]){ 
        forced = 1; 
        if(sum[0] > sum[1]) 
            par = 0; 
        else 
            par = 1; 
    }
    int konce = 0; 
    vector<int> kon; 
    if(v[0] == v[1]){
        kon.push_back(0); 
        konce++; 
        if(forced && par == 1){ 
            cout << "NIE\n"; 
            return; 
        }
    }
    if(v[n-1] == v[n-2]){
        konce++;  
        kon.push_back(n-1); 
        if(forced && (n-1)%2 != par){ 
            cout << "NIE\n"; 
            return; 
        }
    }
    for(int i = 1; i < n-1; i++){ 
        if(v[i] > v[i-1] + v[i+1]+1){ 
            cout << "NIE\n"; 
            return; 
        }
        if(v[i] == v[i-1] + v[i+1] + 1){ 
            konce+=2; 
            kon.push_back(i); 
            kon.push_back(i); 
            if(forced && i%2 != par){ 
                cout << "NIE\n"; 
                return; 
            }
        }
        if(v[i] == v[i-1] + v[i+1] ){ 
            konce+=1;  
            kon.push_back(i); 
            if(forced && i%2 != par){ 
                cout << "NIE\n"; 
                return; 
            }
        }
    } 
    
    if(konce > 2){ 
        cout << "NIE\n"; 
        return; 
    }  
    if(kon.size() <= 1){ 
        cout << "TAK\n"; 
        return; 
    }
    if(kon[0] > kon[1])
        swap(kon[0], kon[1]);  
   //cout << "konce: " << kon[0] << " " << kon[1] << "\n"; 
    ll licz = 0;
    for(int i = 0; i < kon[0]; i++){ 
        if(v[i] < 2*licz || (i > 0 && kon[i] < kon[i-1]) ){ 
            cout << "NIE\n"; 
            return; 
        }
        if(v[i]%2 == 1){ 
            licz++; 
        }
    } 
    licz = 0; 
    for(int i = n-1; i > kon[1]; i--){ 
        if(v[i] < 2*licz || (i < n-1 && kon[i] < kon[i+1])){ 
            cout << "NIE\n"; 
            return; 
        }
        if(v[i]%2 == 1){ 
            licz++; 
        }
    }
   /* for(int i = kon[0] + 1; i < kon[1]; i++){ 
        if(v[i]%2 == 0){ 
            cout << "NIE\n"; 
            return; 
        }
    }
    */ 
    cout << "TAK\n"; 
}

int main(){  
    ios_base::sync_with_stdio(0); 
    cin.tie(0); 
    cout.tie(0); 
    int q; 
    cin >> q; 
    while(q--){ 
        solve(); 
    }
}