题目描述

题目译自 PA 2025 Runda 2 Wyliczanka

在 Bajtosia 的幼儿园里，玩具多得让人眼花缭乱，小女孩 Bajtosia 有时候真不知道该挑哪一个玩。为了让自己轻松决定，她想出了一个办法——用念儿歌来选玩具。

假设某天她要从 $n$ 个玩具中挑一个，她会把它们排成一排，编号从 $1$ 到 $n$。她先指向某个玩具，然后一边念儿歌，一边按每节拍在玩具间移动——要么移到前一个，要么移到后一个（如果在 $1$ 号玩具，只能移到 $2$；如果在 $n$ 号玩具，只能移到 $n-1$）。儿歌念完时，她指向的最后一个玩具就是当天要玩的。

Bajtosia 会记下念儿歌时每个玩具被指了多少次：第 $i$ 个玩具被指了 $a_{i}$ 次。请你帮她检查一下，她有没有记错——也就是说，给定她记下的序列 $a_{1}, a_{2}, \ldots, a_{n}$，判断是否存在一个儿歌能匹配这个记录。

这种情况持续了 $t$ 天，每天玩具数量和儿歌都不一样。

输入格式

输入的第一行包含一个整数 $t$ $(1 \leq t \leq 100000)$，表示 Bajtosia 用儿歌选玩具的天数。接下来是 $t$ 个描述，每天一个。

每个描述的第一行包含一个整数 $n$ $(1 \leq n \leq 1000000)$，表示那天参与儿歌选择的玩具数量。第二行包含 $n$ 个整数 $a_{1}, a_{2}, \ldots, a_{n}$ $(0 \leq a_{i} \leq 10^{9})$，表示 Bajtosia 记录的每个玩具被指的次数。保证至少有一个 $a_{i}$ 不为 $0$。

所有 $t$ 天的 $n$ 之和不超过 $1000000$。

输出格式

输出 $t$ 行，每行包含一个字符串 TAK 或 NIE。TAK 表示存在一个儿歌匹配 Bajtosia 的记录，NIE 表示不存在。

7
3
1 3 1
2
5 7
3
0 1 0
1
2
6
3 3 2 1 0 0
5
1 3 2 2 3
3
1 0 1

TAK
NIE
TAK
NIE
TAK
NIE
NIE

第一天，字节西亚在念儿歌时可以依次指向玩具 $2,1,2,3,2$。

第三天，她用了很短的儿歌，然后开始玩第一个指向的玩具。

第五天，她可以依次指向玩具 $1,2,3,4,3,2,1,2,1$。

对于其他几天，不存在匹配的儿歌。