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
#include <iostream>
#include <vector>

bool is_valid_rhyme(const std::vector<long long>& a) {
    int n = a.size();
    
    // Special case: single toy
    if (n == 1) return a[0] == 1;
    
    // Calculate total points
    long long total = 0;
    for (const auto& count : a) total += count;
    
    // Calculate transitions between toys
    std::vector<long long> transitions(n - 1, 0);
    
    // Start from the leftmost boundary
    transitions[0] = a[0];
    
    // Calculate intermediate transitions
    for (int i = 1; i < n - 1; i++) {
        // For middle positions, entries = exits, so:
        // transitions[i-1] + transitions[i] = 2 * a[i]
        transitions[i] = 2 * a[i] - transitions[i-1];
        if (transitions[i] < 0) return false;
    }
    
    // The number of transitions at the rightmost boundary must equal a[n-1]
    if (transitions[n-2] != a[n-1]) return false;
    
    // Total transitions should be total-1 (one less than total points)
    long long total_transitions = 0;
    for (const auto& t : transitions) total_transitions += t;
    
    return total_transitions == total - 1;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int t;
    std::cin >> t;
    
    while (t--) {
        int n;
        std::cin >> n;
        
        std::vector<long long> a(n);
        for (int i = 0; i < n; i++) {
            std::cin >> a[i];
        }
        
        std::cout << (is_valid_rhyme(a) ? "TAK" : "NIE") << '\n';
    }
    
    return 0;
}