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