4308. 区间消除

【题目描述】

给定一个长度为 $n$ 的序列 $A$。

我们定义一个消除操作：对于一个序列长度为 $n$ 的序列 $B$ 以及一个分割点 $k$ （$n > 1, k < n$），将 $B$ 分割成 $B_{[1, k]}$ 和 $B_{(k, n]}$，分别计算两个序列的异或和，然后保留较大 的那个区间（如果两个区间异或和相同，那么任选一个保留）。

不断进行消除操作直到序列长度最终为 $1$，即只有一个位置被保留下来。

对于每个位置 $i$，查询 $i$ 是否可以称为被保留下来的位置。

【输入格式】

第一行一个整数 $q$ 表示查询次数。

对于每组查询：

一行一个整数 $n$ 表示序列长度为 $n$。

接下来一行 $n$ 个整数表示序列 $A$。

【输出格式】

输出 $q$ 行。

一行一个长度为 $n$ 的 01 串表示每个位置是否可以被保留到最后。

【样例输入】

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

【数据规模与约定】

数据按以下方式分组：

第一组 $16pts$：满足 $q = 1, n \le 10$。

第二组 $8pts$：满足 $q = 1, n \le 3000, A_i = 0/1$。

第三组 $16pts$：满足 $q \le 10, n \le 100$。

第四组 $60pts$：满足 $q \le 10, n \le 3000$。

对于所有数据，有 $A_i < 2^{60}$。

大洋里