NIT and TIN Game

You are given a binary sequence a₁, a₂, \(\ldots\), a_n\) of length \(n\) consisting of 0s and 1s. The sequence is guaranteed to contain an even number of 1s.

Two players, NIT and TIN, play a game alternately, with NIT moving first. In each move, the current player performs the following operation:

1. Select an index \(i\) (\(1\le i\le n\)) such that the prefix \([1,i]\) contains an odd number of 1s. (That is, \(\sum_{k=1}^i a_k \equiv 1 \pmod{2}\)).
2. Select an index \(j\) with \(i < j \le n\).
3. Flip both \(a_i\) and \(a_j\) (i.e. change 0 to 1 and 1 to 0).

The game ends when the entire sequence becomes 0, at which point the player who is about to move loses.

It can be proved that the game always terminates. Both players play optimally. Determine who will win the game: NIT or TIN.

Hint: Note that an optimal move is one which removes two 1s from the sequence. Since the number of 1s is even, one can show that if the total number of moves \(=\frac{\text{number of ones}}{2}\) is odd then NIT wins; otherwise TIN wins. Do remember to handle the case where the sequence is already all zeros.

All formulae are in \(\LaTeX\) format.

inputFormat

The first line contains an integer \(n\) \( (1 \le n \le 10^9)\) representing the length of the sequence. The second line contains a binary string of length \(n\) consisting only of characters '0' and '1'. It is guaranteed that the number of '1's in the sequence is even and does not exceed \(2 \times 10^5\).

outputFormat

Output a single line containing either NIT or TIN — the winner of the game when both players play optimally.

sample

2
11

NIT