{"problem":{"name":"[RC-07] Game Theory","description":{"content":"给出长度为 $n$ 的 `01` 序列 $a_{1\\sim n}$，**序列中有偶数个 `1`**。NIT 和 TIN 轮流做以下操作，NIT 先手： - 选择位置 $i\\ (1\\le i\\le n)$，满足区间 $[1,i]$ 中有奇数个 `1`。再选择位置 $j\\ (i<j\\le n)$。将 $a_i,a_j$ 都取反（即，`0` 变 `1`，`1` 变 `0`） 当整个序列中的所有元素都","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9003"},"statements":[{"statement_type":"Markdown","content":"给出长度为 $n$ 的 `01` 序列 $a_{1\\sim n}$，**序列中有偶数个 `1`**。NIT 和 TIN 轮流做以下操作，NIT 先手：\n\n- 选择位置 $i\\ (1\\le i\\le n)$，满足区间 $[1,i]$ 中有奇数个 `1`。再选择位置 $j\\ (i<j\\le n)$。将 $a_i,a_j$ 都取反（即，`0` 变 `1`，`1` 变 `0`）\n\n当整个序列中的所有元素都变为 `0` 时，当前轮到的人就无法操作，他就输了。假设 NIT 和 TIN 都*绝顶*聪明，谁会赢？可以证明，游戏总会结束。\n\n$n$ 可能很大，但序列中 $1$ 的个数不超过 $2\\times 10^5$。\n\n## Input\n\n**本题有多组数据。**\n\n输入的第一行是数据组数 $T$。\n\n接下来是每组数据的描述。每组数据的第一行是两个正整数 $n,m$，$m$ 为序列中 `1` 的个数，保证 $m$ 是偶数。\n\n接下来一行 $m$ 个**递增**的正整数，描述这些 `1` 的下标，下标从 $1$ 开始。\n\n## Output\n\n对每组数据，输出一行一个字符串 `NIT` 或 `TIN`，表示赢家的名字。\n\n[samples]\n\n## Note\n\n**样例解释**\n\n第一组数据中，NIT 选择 $i=1,j=3$ 就能把全部位置都变成 0，使得 TIN 无法操作。\n\n第二组数据中，无论 NIT 先手怎么操作，都会剩下恰好两个 1 的位置。TIN 只需要选择这两个剩下的位置，就可以把全部位置都变成 0。\n\n第三组数据中，一种可能的游戏进程如下（注意该进程里，每一步不一定是最优的）：\n\n- NIT 选择 $i=2,j=3$ 并将这两个位置取反。现在 \n`1` 的位置在 $1,2,7,8$。\n- TIN 选择 $i=7,j=9$ 并将这两个位置取反。现在 \n`1` 的位置在 $1,2,8,9$。\n- NIT 选择 $i=1,j=5$ 并将这两个位置取反。现在 \n`1` 的位置在 $2,5,8,9$。\n- TIN 选择 $i=3,j=4$ 并将这两个位置取反。现在 \n`1` 的位置在 $2,3,4,5,8,9$。\n- NIT 选择 $i=4,j=5$ 并将这两个位置取反。现在 \n`1` 的位置在 $2,3,8,9$。\n- TIN 选择 $i=2,j=9$ 并将这两个位置取反。现在 \n`1` 的位置在 $3,8$。\n- NIT 选择 $i=3,j=8$ 并将这两个位置取反。现在序列里没有 `1` 了。\n- TIN 无法操作，NIT 获胜。\n\n**数据范围**\n\n对于所有数据，$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$。保证 $m$ 是偶数，保证为 `1` 的下标是递增顺序给出的。\n\n- 子任务 1（$1$ 分）$T\\le 10^3$，$n\\le 10$。\n- 子任务 2（$9$ 分）序列中全是 `1`。\n- 子任务 3（$40$ 分）$T\\le 100$，$n\\le 100$。\n- 子任务 4（$10$ 分）$\\sum n\\le 10^6$。\n- 子任务 5（$40$ 分）没有任何附加限制。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9003","tags":["O2优化"],"sample_group":[["3\n4 2\n1 3\n4 4\n1 2 3 4\n10 4\n1 3 7 8","NIT\nTIN\nNIT"]],"created_at":"2026-03-03 11:09:25"}}