Вам дан массив из \(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\).
Выходные данные
Для каждого набора входных данных выведите строку длины \(n\), где \(i\)-й символ равен 1, если можно добиться \(l = r = i\), и 0 в противном случае.
Примечание
В первом тесте возможно добиться равенств \(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\).
- Мы можем выбрать \(k = 3\) и присвоить \(r = k = 3\), поскольку \((3 \oplus 2 \oplus 1) = 0 \ge 0 = (3 \oplus 7 \oplus 4)\);
- Затем мы можем выбрать \(k = 1\) и присвоить \(l = k + 1 = 2\), так как \(3 \le 3 = (2 \oplus 1)\);
- Наконец, мы можем выбрать \(k = 2\) и присвоить \(r = k = 2\), поскольку \(2 \ge 1\).