CF1863F.Divide, XOR, and Conquer

You are given an array of $n$ integers $a_1, a_2, \ldots, a_n$.

In one operation you split the array into two parts: a non-empty prefix and a non-empty suffix. The value of each part is the bitwise XOR of all elements in it. Next, discard the part with the smaller value. If both parts have equal values, you can choose which one to discard. Replace the array with the remaining part.

The operations are being performed until the length of the array becomes $1$. For each $i$ ($1 \le i \le n$), determine whether it is possible to achieve the state when only the $i$-th element (with respect to the original numbering) remains.

Formally, you have two numbers $l$ and $r$, initially $l = 1$ and $r = n$. The current state of the array is $[a_l, a_{l+1}, \ldots, a_r]$.

As long as $l \lt r$, you apply the following operation:

• Choose an arbitrary $k$ from the set ${l, l + 1, \ldots, r - 1}$. Denote $x = a_l \oplus a_{l + 1} \oplus \ldots \oplus a_k$ and $y = a_{k + 1} \oplus a_{k + 2} \oplus \ldots \oplus a_{r}$, where $\oplus$ denotes the bitwise XOR operation.
• If $x \lt y$, set $l = k + 1$.
• If $x \gt y$, set $r = k$.
• If $x = y$, either set $l = k + 1$, or set $r = k$.

For each $i$ ($1 \le i \le n$), determine whether it is possible to achieve $l = r = i$.

给你一个包含 $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 \lt r$，就执行如下操作：

• 任选一个 $k$，满足 $k \in \{l, l + 1, \ldots, r - 1\}$。记 $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 \lt y$，则令 $l = k + 1$；
• 若 $x \gt y$，则令 $r = k$；
• 若 $x = y$，则可任选令 $l = k + 1$ 或令 $r = k$。

对每个 $i$（$1 \le i \le n$），判断是否可能达到 $l = r = i$ 的状态。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10\,000$). The description of the test cases follows.

The first line of each test case contains one integer $n$ ($1 \le n \le 10\,000$).

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \lt 2^{60}$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $10\,000$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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 \lt 2^{60}$）。

保证所有测试用例的 $n$ 值之和不超过 $10\,000$。

For each test case, output a single string of length $n$ where the $i$-th element is equal to 1 if it is possible to achieve $l = r = i$ and is equal to 0 otherwise.

对于每个测试用例，输出一个长度为 $n$ 的字符串，其中第 $i$ 个元素在能够实现 $l = r = i$ 时为 1，否则为 0。

In the first test case, it is possible to achieve $l = r = i$ for any $i$ from $1$ to $n$:

• for $i=1$: $[1; 6] \rightarrow [1; 4] \rightarrow [1; 1]$;
• for $i=2$: $[1; 6] \rightarrow [1; 3] \rightarrow [2; 3] \rightarrow [2; 2]$;
• for $i=3$: $[1; 6] \rightarrow [1; 3] \rightarrow [3; 3]$;
• for $i=4$: $[1; 6] \rightarrow [1; 4] \rightarrow [4; 4]$;
• for $i=5$: $[1; 6] \rightarrow [5; 6] \rightarrow [5; 5]$;
• for $i=6$: $[1; 6] \rightarrow [6; 6]$.

Let's take a closer look at $i = 2$. Initially $l = 1$, $r = 6$.

1. We can choose $k = 3$ and set $r = k = 3$ since $(3 \oplus 2 \oplus 1) = 0 \ge 0 = (3 \oplus 7 \oplus 4)$;
2. Next, we can choose $k = 1$ and set $l = k + 1 = 2$ since $3 \le 3 = (2 \oplus 1)$;
3. Finally, we can choose $k = 2$ and set $r = k = 2$ since $2 \ge 1$.

在第一个测试用例中，对于任意 $i$（$1 \le i \le n$），均可实现 $l = r = i$：

• 对于 $i=1$：$[1; 6] \rightarrow [1; 4] \rightarrow [1; 1]$；
• 对于 $i=2$：$[1; 6] \rightarrow [1; 3] \rightarrow [2; 3] \rightarrow [2; 2]$；
• 对于 $i=3$：$[1; 6] \rightarrow [1; 3] \rightarrow [3; 3]$；
• 对于 $i=4$：$[1; 6] \rightarrow [1; 4] \rightarrow [4; 4]$；
• 对于 $i=5$：$[1; 6] \rightarrow [5; 6] \rightarrow [5; 5]$；
• 对于 $i=6$：$[1; 6] \rightarrow [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$。