给你一个 $$$n$$$ 整数数组 $$$a_1, a_2, \ldots, a_n$$$。
在一次操作中,您将数组分为两部分:非空前缀和非空后缀。每个部分的值是其中所有元素的按位异或。接下来,丢弃值较小的部分。如果两个部分的值相等,您可以选择丢弃哪一个。将数组替换为剩余部分。
正在执行操作,直到数组的长度变为$$$1$$$。对于每个 $$$i$$$ ($$$1 \le i \le n$$$),确定是否可以达到仅剩下第 $$$i$$$ 个元素(相对于原始编号)时的状态。
形式上,您有两个数字 $$$l$$$ 和 $$$r$$$,最初 $$$l = 1$$$ 和 $$$r = n$$$。数组的当前状态是$$$[a_l, a_{l+1}, \ldots, a_r]$$$。
只要 $$$l < r$$$,就应用以下操作:
- 从集合 $$$\{l, l + 1, \ldots, r - 1\}$$$ 中选择任意 $$$k$$$。表示 $$$x = a_l \oplus a_{l + 1} \oplus \ldots \oplus a_k$$$ 和 $$$y = a_{k + 1} \oplus a_{k + 2} \oplus \ldots \oplus a_{r}$$$,其中 $$$\oplus$$$ 表示按位异或运算。
- 如果 $$$x < y$$$,则设置 $$$l = k + 1$$$。
- 如果 $$$x > y$$$,则设置 $$$r = k$$$。
- 如果 $$$x = y$$$,则设置 $$$l = k + 1$$$,或设置 $$$r = k$$$。
对于每个$$$i$$$ ($$$1 \le i \le n$$$),判断是否可以实现$$$l = r = i$$$。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10\,000$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10\,000$$$)。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i < 2^{60}$$$)。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$10\,000$$$。
输出
对于每个测试用例,输出长度为 $$$n$$$ 的单个字符串,其中如果可以实现 $$$l = r = i$$$,则第 $$$i$$$ 个元素等于 1,否则等于 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$$$ 到 $$$n$$$ 的任何 $$$i$$$ 可以实现 $$$l = r = i$$$:
- 对于 $$$i=1$$$: $$$[1; 6] \右箭头 [1; 4] \右箭头 [1; 1]$$$;
- 对于 $$$i=2$$$: $$$[1; 6] \右箭头 [1; 3] \右箭头 [2; 3] \右箭头 [2; 2]$$$;
- 对于 $$$i=3$$$: $$$[1; 6] \右箭头 [1; 3] \右箭头 [3; 3]$$$;
- 对于 $$$i=4$$$: $$$[1; 6] \右箭头 [1; 4] \右箭头 [4; 4]$$$;
- 对于 $$$i=5$$$: $$$[1; 6] \右箭头 [5; 6] \右箭头 [5; 5]$$$;
- 对于 $$$i=6$$$: $$$[1; 6] \右箭头 [6; 6]$$$。
让我们仔细看看 $$$i = 2$$$。最初$$$l = 1$$$,$$$r = 6$$$。
1. 我们可以选择 $$$k = 3$$$ 并设置 $$$r = k = 3$$$,因为 $$$(3 \oplus 2 \oplus 1) = 0 \ge 0 = (3 \oplus 7 \oplus 4)$$$;
2. 接下来,我们可以选择 $$$k = 1$$$ 并设置 $$$l = k + 1 = 2$$$,因为 $$$3 \le 3 = (2 \oplus 1)$$$;
3. 最后,我们可以选择 $$$k = 2$$$ 并设置 $$$r = k = 2$$$,因为 $$$2 \ge 1$$$。