P9003 [RC-07] Game Theory

You are given a `01` sequence $a_{1\sim n}$ of length $n$, and **the sequence contains an even number of `1`**. NIT and TIN take turns performing the following operation, with NIT going first: - Choose a position $i\ (1\le i\le n)$ such that the interval $[1,i]$ contains an odd number of `1`. Then choose a position $j\ (i

**This problem has multiple test cases.** The first line of input contains the number of test cases $T$. Then follows the description of each test case. The first line of each test case contains two positive integers $n,m$, where $m$ is the number of `1` in the sequence, and it is guaranteed that $m$ is even. The next line contains $m$ **strictly increasing** positive integers describing the indices of these `1`. Indices start from $1$.

For each test case, output one line with a string `NIT` or `TIN`, indicating the winner’s name.

**Explanation of the samples** In the first test case, NIT can choose $i=1,j=3$ to turn all positions into 0, making TIN unable to move. In the second test case, no matter how NIT plays first, there will be exactly two positions with 1 left. TIN only needs to choose these two remaining positions to turn all positions into 0. In the third test case, one possible game process is as follows (note that in this process, each move is not necessarily optimal): - NIT chooses $i=2,j=3$ and flips these two positions. Now the positions of `1` are $1,2,7,8$. - TIN chooses $i=7,j=9$ and flips these two positions. Now the positions of `1` are $1,2,8,9$. - NIT chooses $i=1,j=5$ and flips these two positions. Now the positions of `1` are $2,5,8,9$. - TIN chooses $i=3,j=4$ and flips these two positions. Now the positions of `1` are $2,3,4,5,8,9$. - NIT chooses $i=4,j=5$ and flips these two positions. Now the positions of `1` are $2,3,8,9$. - TIN chooses $i=2,j=9$ and flips these two positions. Now the positions of `1` are $3,8$. - NIT chooses $i=3,j=8$ and flips these two positions. Now there is no `1` in the sequence. - TIN cannot move, and NIT wins. **Constraints** For all testdata, $1\le T\le 10^4$, $1\le n\le 10^{18}$, $2\le m\le 2\times 10^5$, $\sum m\le 10^6$. It is guaranteed that $m$ is even, and the indices that are `1` are given in increasing order. - Subtask 1 ($1$ point): $T\le 10^3$, $n\le 10$. - Subtask 2 ($9$ points): The sequence is all `1`. - Subtask 3 ($40$ points): $T\le 100$, $n\le 100$. - Subtask 4 ($10$ points): $\sum n\le 10^6$. - Subtask 5 ($40$ points): No additional constraints. Translated by ChatGPT 5