题目

给定一个长度为 $n$ 的整数数组 $a_1,a_2,\ldots,a_n$。

一次操作中，你把当前数组分成两段：非空前缀和非空后缀。两段的“价值”分别等于各自所有元素的按位异或（XOR）值。然后：

• 丢弃价值较小的那一段；
• 若两段价值相等，则你可以任选丢弃其中一段；
• 用剩下的那一段替换当前数组。

不断重复操作，直到数组长度变为 $1$。

对每个 $i\ (1\le i\le n)$，判断是否存在一种操作序列，使得最终只剩下原数组中的第 $i$ 个元素。

更形式化地：维护两个指针 $l,r$，初始 $l=1,r=n$，当前数组为 $[a_l,a_{l+1},\ldots,a_r]$。当 $l<r$ 时执行：

• 任选 $k\in{l,l+1,\ldots,r-1}$；
• 令$$x=a_l\oplus a_{l+1}\oplus\cdots\oplus a_k,\qquad y=a_{k+1}\oplus a_{k+2}\oplus\cdots\oplus a_r$$
• 若 $x<y$，令 $l=k+1$；
• 若 $x>y$，令 $r=k$；
• 若 $x=y$，可任选令 $l=k+1$ 或 $r=k$。

对每个 $i$，判断是否可能达到 $l=r=i$。

输入格式

多组测试。

• 第一行一个整数 $t$，表示测试组数。

• 接下来 $t$ 组测试，每组：

  • 第一行一个整数 $n$；
  • 第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

对每组测试，输出一个长度为 $n$ 的 01 串：第 $i$ 位为 1 表示可以最终只剩下第 $i$ 个元素，否则为 0。

6
6
3 2 1 3 7 4
5
1 1 1 1 1
10
1 2 4 8 4 1 2 3 4 5
5
0 0 0 0 0
5
1 2 3 0 1
1
100500

111111
10101
0001000000
11111
11001
1

约束

• $1\le t\le 10^4$
• $1\le n\le 10^4$
• $0\le a_i<2^{60}$
• 所有测试的 $n$ 之和不超过 $10^4$

部分分

说明：所有数据文件都满足“每个文件内所有测试的 $\sum n\le 10000$”。