题目描述

小 L 和小 K 发明了一种新的游戏。游戏将在一行 $n$ 个格子上进行，代表 $n$ 个城市，分别为城市 $1,2,\dots,n$。初始，城市 $i$ 有士兵 $a_i$ 人。两人约定，前 $m$ 个编号的城市是小 L 的地盘，其他城市是小 K 的地盘。

两人将交替进行操作，小 L 先手。轮到该方操作时，可以作出如下行动之一：

• 转移：选择己方地盘上的两个城市 $x,y$，满足 $|x-y|=1$，把城市 $x$ 的士兵全部转移到城市 $y$，即同时令 $a_y\leftarrow a_x+a_y$，$a_x\leftarrow 0$。
• 攻占：选择己方地盘上的城市 $x$ 和对方地盘上的城市 $y$，满足 $|x-y|=1$ 且轮到小 L 操作时需满足 $a_x>a_y$，轮到小 K 操作时需满足 $a_x\geq a_y$，攻占对方的城市 $y$，把城市 $x$ 的士兵全部转移到城市 $y$，即同时令 $a_y\leftarrow a_x+a_y$，$a_x\leftarrow 0$，把城市 $y$ 归到己方的地盘上。
• 不进行任何操作。

当一方将所有城市归为己方地盘时，该方获胜。如果两人都绝顶聪明的话，谁将获胜？请你对于 $m=1,2,\dots,n-1$ 分别输出 $m$ 取该值时问题的答案。

可以证明在双方绝顶聪明的情况下，博弈一定可以在有限次操作内结束。

输入格式

本题包含多组测试数据。

第一行，一个正整数 $T$，表示测试数据组数。对于每组测试数据：

• 第一行，一个正整数 $n$，表示城市数量。
• 第二行，$n$ 个正整数 $a_1, \ldots, a_n$，表示每个城市的士兵数量。

输出格式

对于每组测试数据，一行一个长度为 $n-1$ 的 01 字符串 $S$，分别表示 $m=1,2,\dots,n-1$ 时的答案。对于每一个 $m$，若小 L 获胜，输出 1，否则输出 0。

1
7
4 3 1 6 3 4 1

000111

提示

【样例解释 #1】

初始 $a=\{4,3,1,6,3,4,1\}$。

当 $m=1$ 时，小 L 的最优策略是选择攻占操作，取 $x=1$ 和 $y=2$，这次操作后序列 $a=\{0,7,1,6,3,4,1\}$，城市 $2$ 归到小 L 的地盘上。接下来，小 K 只需不断地选择转移操作，把第 $3$ 个城市往后的所有士兵经过 $4$ 轮都转移到第 $7$ 个城市，此时 $a_7=15$，小 L 一方无论如何最多只可能有 $7$ 个士兵。小 K 无论如何都能取得胜利。

当 $m=4$ 时，小 L 只需要把第 $4$ 个城市向前的所有士兵经过 $3$ 轮都转移到城市 $1$，此时 $a_1=14$，对方最多只可能有 $8$ 个士兵。小 L 无论如何都能取得胜利。

【样例 #2】

见选手目录下的 $\textbf{\textit{war/war2.in}}$ 与 $\textbf{\textit{war/war2.ans}}$。

该样例满足测试点 $1$ 的约束条件。

【样例 #3】

见选手目录下的 $\textbf{\textit{war/war3.in}}$ 与 $\textbf{\textit{war/war3.ans}}$。

该样例满足测试点 $4\sim 7$ 的约束条件。

【样例 #4】

见选手目录下的 $\textbf{\textit{war/war4.in}}$ 与 $\textbf{\textit{war/war4.ans}}$。

该样例满足测试点 $11\sim 13$ 的约束条件。

【样例 #5】

见选手目录下的 $\textbf{\textit{war/war5.in}}$ 与 $\textbf{\textit{war/war5.ans}}$。

该样例满足测试点 $14\sim 18$ 的约束条件。

【样例 #6】

见选手目录下的 $\textbf{\textit{war/war6.in}}$ 与 $\textbf{\textit{war/war6.ans}}$。

该样例满足测试点 $19\sim 25$ 的约束条件。

【数据范围】

本题共 $25$ 个测试点，每个 $4$ 分。

对于所有测试数据，保证：

• $1\le T\le 20$；
• $2\leq n\leq10^5$；
• $1\leq a_i\leq10^9$。

::cute-table{tuack}

测试点编号	$n \le$	特殊性质
$1$	$2$	无
$2, 3$	$4$	^
$4\sim 7$	$10$
$8\sim 10$	$10^5$	A
$11\sim 13$	^	B
$14\sim 18$		C
$19\sim 25$		无

特殊性质 A：对于所有 $1 \le i \le n$ 均有 $a_i=1$。
特殊性质 B：对于所有 $1 \le i < n$ 均有 $a_i\leq a_{i+1}$。
特殊性质 C：对于所有 $1 \le i \le n - 2$ 均有 $a_i+a_{i+1}> a_{i+2}$。