分割、异或与征服

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

给定一个长度为 $n$ 的整数数组 $a$。

当前保留的数组始终是原数组的一个连续区间 $[l,r]$。当 $l<r$ 时，可以任选 $k$（$l\le k<r$），把区间分为 $[l,k]$ 与 $[k+1,r]$。令两部分的元素异或和分别为 $x$ 和 $y$：

• 若 $x<y$，丢弃左边部分；
• 若 $x>y$，丢弃右边部分；
• 若 $x=y$，可以任选一边丢弃。

不断操作直到区间只剩一个元素。请对每个位置 $i$ 判断，是否存在一种操作方案使最后只剩下原数组的第 $i$ 个元素。

输入格式

第一行一个整数 $t$，表示测试用例数量。

每个测试用例第一行一个整数 $n$；第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

对每个测试用例输出一个长度为 $n$ 的二进制字符串。第 $i$ 个字符为 1 表示第 $i$ 个元素可能成为最后剩下的元素，否则为 0。

样例输入 1

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

样例输出 1

111111
10101
0001000000
11111
11001
1

数据范围

$1\le t\le10^4$，$1\le n\le10^4$，$0\le a_i<2^{60}$，且所有测试用例的 $n$ 之和不超过 $10^4$。