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
import sys, numpy as np

def solve():
    data = sys.stdin.buffer.read().split()
    if not data: 
        return
    t = int(data[0])
    pos = 1
    out_lines = []
    # We'll use a large constant for "infinity" for our minimum computations.
    INF = 10**18

    # Process each test case:
    for _ in range(t):
        n = int(data[pos]); pos += 1
        # read n integers as Python ints (they can be large but not huge)
        arr = np.array(list(map(int, data[pos:pos+n])), dtype=np.int64)
        pos += n

        # If n==0 (should not happen) or no toy is visited (all zeros) -> not valid.
        if n == 0 or np.all(arr == 0):
            out_lines.append("NIE")
            continue

        # Find the leftmost and rightmost indices where the count is nonzero.
        # (Because if some toys are never pointed to, the valid walk is confined to a contiguous block.)
        nonzero = np.flatnonzero(arr)
        L0 = int(nonzero[0])
        R0 = int(nonzero[-1])
        # Check that outside [L0,R0] all counts are zero – if not, no valid walk.
        if L0 > 0 and np.any(arr[:L0] != 0):
            out_lines.append("NIE")
            continue
        if R0 < n-1 and np.any(arr[R0+1:] != 0):
            out_lines.append("NIE")
            continue

        m = R0 - L0 + 1  # length of visited block
        # Let c be the block of counts for the visited toys.
        c = arr[L0:R0+1].astype(np.int64)
        # We now define an alternating “flow” sequence B of length m.
        # It is defined by:
        #   B[0] = c[0]
        #   B[k] = c[k] - B[k-1]   for k >= 1.
        # In closed form one gets:
        #   B[k] = (-1)**k * (c[0] - c[1] + c[2] - ... +/- c[k])
        # We compute B vectorized via cumulative sum:
        idx = np.arange(m, dtype=np.int64)
        signs = np.power(-1, idx)   # array: [1, -1, 1, -1, ...]
        # Compute cumsum of (signs * c), then multiply by signs:
        B = signs * np.cumsum(signs * c)
        # For a valid walk, the flow balance at the final visited toy must vanish.
        # In our formulation the “adjusted” flows (after subtracting 1 at the chosen starting toy)
        # must yield zero at the end.
        # It turns out (by a short algebra) that a necessary condition is that B[m-1] equals either 1 or -1.
        finalB = int(B[m-1])
        if finalB not in (1, -1):
            out_lines.append("NIE")
            continue

        # The idea is that if we “subtract 1” (the effect of starting at that toy) at a candidate index s (0-indexed in the block),
        # then for indices j >= s the adjusted flow becomes: f[j] = B[j] - (-1)^(j-s).
        # In a valid walk we require that for j in [s, m-2] the adjusted flows f[j] are strictly positive,
        # and that f[m-1] == 0.
        # It turns out (after a short algebra) that the candidate s is possible only if the “pivot” (i.e. starting toy)
        # is chosen with a fixed parity. In fact, one may show that (-1)^s must equal:
        #      required_x = B[m-1] * (-1)^(m-1)
        required_x = finalB * (1 if ((m-1) % 2 == 0) else -1)
        # Thus, if required_x==1, candidate s must be even; if required_x==-1, candidate s must be odd.
        # We now prepare two sets of conditions:
        # (a) For indices j < s (i.e. before the starting toy) the unadjusted flow B[j] must be > 0.
        #     (In the case s==0 there is no such constraint – except that when m>1, one must have f[0]=B[0]-1 > 0.)
        # (b) For indices j from s to m-2, the adjusted value Q(j,s) = B[j] - (-1)^(j-s)
        #     must be > 0; note that by our transformation this is equivalent to:
        #         B[j] - required_x * (-1)^j  > 0   for j = s, s+1, …, m-2.
        # And finally the condition at the end (j = m-1) then automatically becomes B[m-1] - required_x*(-1)^(m-1)==0.
        #
        # We precompute the prefix minimum of B:
        P = np.empty(m, dtype=np.int64)
        P[0] = B[0]
        for i in range(1, m):
            # we need strict positivity for j < s so we compute min(B[0..i])
            P[i] = P[i-1] if P[i-1] < B[i] else B[i]
        # Now precompute Q[j] = B[j] - required_x * (-1)^j for j = 0,..., m-2.
        if m > 1:
            j_idx = np.arange(m-1, dtype=np.int64)
            Q = B[:m-1] - np.power(required_x, 0) * np.power(-1, j_idx)  # np.power(required_x,0) is 1; this is just: B[j] - required_x * (-1)^j.
            # Compute the suffix minimum S[k] = min{ Q[j] for j=k..m-2 } for k = 0,..., m-1.
            S = np.empty(m, dtype=np.int64)
            S[m-2] = Q[m-2]
            for i in range(m-3, -1, -1):
                S[i] = Q[i] if Q[i] < S[i+1] else S[i+1]
            S[m-1] = INF  # for candidate s = m-1, no suffix condition (we then require f[m-1]==0, which is automatic)
        else:
            S = np.array([INF], dtype=np.int64)
        # Identify candidate indices k in 0..m-1 that have the required parity,
        # i.e. such that (-1)^k == required_x.
        parities = np.power(-1, np.arange(m))
        cand_idx = np.flatnonzero(parities == required_x)
        valid = False
        for k in cand_idx:
            # For candidate corresponding to s = L0 + k:
            if m == 1:
                # For block length 1, we require B[0] == 1 (which is true if requiredB==1)
                if B[0] == 1:
                    valid = True
                    break
            else:
                # For candidate k (with m>1):
                # If k == 0 then the adjusted f[0] would be B[0]-(-1)^(0)= B[0]-1, which must be >0.
                if k == 0:
                    if B[0] <= 1:
                        continue
                else:
                    if P[k-1] <= 0:
                        continue
                # Now check the suffix condition: we require that the minimum over indices j=k..m-2 of (B[j] - required_x * (-1)^j) is > 0.
                if S[k] <= 0:
                    continue
                # (The final condition at j = m-1 is automatically satisfied by our choice of required_x.)
                valid = True
                break
        out_lines.append("TAK" if valid else "NIE")
    sys.stdout.write("\n".join(out_lines))

if __name__ == '__main__':
    solve()