F. Разделяй, считай XOR и властвуй
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив из $$$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 < r$$$, вы применяете следующую операцию:

  • Выбрать произвольное $$$k$$$ из множества $$$\{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 < 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$$$, где $$$i$$$-й символ равен 1, если можно добиться $$$l = r = i$$$, и 0 в противном случае.

Пример
Входные данные
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
Примечание

В первом тесте возможно добиться равенств $$$l = r = i$$$ для всех $$$i$$$ от $$$1$$$ до $$$n$$$:

  • при $$$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$$$.