310637: CF1863F. Divide, XOR, and Conquer

F. Divide, XOR, and Conquertime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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 < 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 < y$, set $l = k + 1$.
• If $x > 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$.

Input

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 < 2^{60}$).

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

Output

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.

ExampleInput

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

Output

111111
10101
0001000000
11111
11001
1

Note

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$.

题目大意：给定一个包含n个整数的数组a_1, a_2, ..., a_n。你可以通过以下操作将数组分割成两部分：非空前缀和非空后缀。每部分的价值是其所有元素的按位异或（XOR）结果。然后，丢弃价值较小的部分。如果两部分的价值相等，可以选择丢弃任意一部分。用剩下的部分替换原数组。重复此操作直到数组长度变为1。对于每个i（1≤i≤n），确定是否可以达到只剩原始编号的第i个元素的状态。

输入数据格式：每个测试用例包含多个测试案例。第一行包含测试案例的数量t（1≤t≤10,000）。接下来是每个测试案例的描述。每个测试案例的第一行包含一个整数n（1≤n≤10,000）。第二行包含n个整数a_1, a_2, ..., a_n（0≤a_i<2^60）。保证所有测试案例的n之和不超过10,000。

输出数据格式：对于每个测试案例，输出一个长度为n的字符串，其中第i个元素为1，如果可以达到l=r=i的状态；否则为0。

请注意，以上内容是根据网页上的题目描述翻译的，具体的编程实现需要根据题目的要求来完成。题目大意：给定一个包含n个整数的数组a_1, a_2, ..., a_n。你可以通过以下操作将数组分割成两部分：非空前缀和非空后缀。每部分的价值是其所有元素的按位异或（XOR）结果。然后，丢弃价值较小的部分。如果两部分的价值相等，可以选择丢弃任意一部分。用剩下的部分替换原数组。重复此操作直到数组长度变为1。对于每个i（1≤i≤n），确定是否可以达到只剩原始编号的第i个元素的状态。 输入数据格式：每个测试用例包含多个测试案例。第一行包含测试案例的数量t（1≤t≤10,000）。接下来是每个测试案例的描述。每个测试案例的第一行包含一个整数n（1≤n≤10,000）。第二行包含n个整数a_1, a_2, ..., a_n（0≤a_i<2^60）。保证所有测试案例的n之和不超过10,000。 输出数据格式：对于每个测试案例，输出一个长度为n的字符串，其中第i个元素为1，如果可以达到l=r=i的状态；否则为0。 请注意，以上内容是根据网页上的题目描述翻译的，具体的编程实现需要根据题目的要求来完成。