Для множества целых чисел \(S\) определим его стоимость как минимальное значение \(x \oplus y\) среди всех пар различных чисел из множества (\(\oplus\) обозначает оператор побитового исключающего ИЛИ). Если в множестве менее двух элементов, его стоимость равна \(2^{30}\).
Вам дано множество целых чисел \(\{a_1, a_2, \dots, a_n\}\). Вы должны разделить его на два множества \(S_1\) и \(S_2\) таким образом, что каждый элемент принадлежит ровно одному из этих двух множеств. Стоимость разделения — это минимум из стоимостей \(S_1\) и \(S_2\).
Найдите разделение с максимальной стоимостью.
Выходные данные
Выведите строку из \(n\) символов 0 и/или 1, описывающую разделение следующим образом: \(i\)-й символ строки должен быть 0, если \(a_i\) принадлежит \(S_1\), в противном случае этот символ должен быть 1.
Если существует несколько оптимальных ответов — выведите любой из них.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
42 13 1337 37 152
|
10001
|
|
2
|
4
1 2 3 4
|
1100
|
|
3
|
2
1 2
|
10
|
|
4
|
8
7 6 5 4 3 2 1 0
|
10010110
|