A21557.SLW-Words

题目描述

函数 $h$ 作用于由数字 $0$ 和 $1$ 组成的字符串，其通过将每一个数字 $0$ 替换为 $1$，将每一个数字 $1$ 替换为字符串 $10$ 来独立且同时地变换字符串 $w$。

例如：

$$h(``1001")=``101110"$$

$$h(``\ ")=``\ "$$

其中例二即把空字符串赋值给空字符串。

注意， $h$ 是一个一对一的函数。

我们用 $h^k$ 表示函数 $h$ 使用 $k$ 次。

特别的， $h^0(w)=w$。

我们对 $k = 0, 1, 2, ...$ 的 $h^k(``0")$ 形式的字符串感兴趣，这个序列为:

$$``0", ``1", ``10", ``101", ``10110", ``10110101", \ldots$$

如果字符串 $x$ 在 $y$ 中以一个连续的（即一个块）子串出现，我们就称 $x$ 为字符串 $y$ 的子串。给出整数 $k_1, k_2, k_3, ..., k_n $ 的序列。你的任务是检查是否有 $m$ ，使 $h^{k_1}(0") \cdot h^{k_2}(0") \cdot \ldots \cdot h^{k_n}(0") $ 形式的字符串是 $h^m(0")$ 的子串。

输入的第一行包含一个整数 $t$ 表示样例数， $1 \leq t \leq 13$。每个样例输入两行，一行 $n$ ， $1 \leq n \leq 100000$ ，另一行为 $n$ 个非负整数 $k_1, k_2, k_3, ..., k_n $，用单个空格分隔。

您的程序应该输出 $t$ 行，每个测试输出一行。如果存在 $m$ 使 $h^{k_1}(0") \cdot h^{k_2}(0") \cdot \ldots \cdot h^{k_n}(0") $ 是 $h^m(0")$ 的子串，就输出 TAK（波兰语中的 yes ），如果不存在 $m$，则输出 NIE（波兰语中的 no ）。