D. Два множества
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Маленький Петя очень любит числа. Недавно мама подарила ему набор из n целых неотрицательных чисел. Больше чем числа Петя любит только играть с маленькой Машей. Он тут же решил поделиться с ней частью своего нового набора. Чтобы вместе детям было еще веселее играть, Петя решил отдать Маше такой набор чисел, для которого выполняются следующие условия:

  • Обозначим через x1 xor всех чисел, которые остались у Пети, а через x2 — xor всех чисел, которые он отдал Маше. Значение (x1 + x2) должно быть как можно больше.
  • Если существует несколько способов разделить набор чисел так, чтобы предыдущее условие выполнялось, то Петя минимизирует значение x1.

Под операцией xor подразумевается побитовое исключающее «ИЛИ», которое обозначается как «xor» в языке Pascal и «^» в C/C++/Java.

Помогите Пете разделить набор требуемым образом. Если существует несколько подходящих разбиений, найдите любое. Обратите внимание, что после того, как Петя отдаст часть своих чисел Маше, у него их может не остаться вовсе. Возможна и обратная ситуация, когда Петя ничего не отдает Маше. В обоих случаях следует считать, что xor пустого набора чисел равен 0.

Входные данные

В первой строке дано целое число n (1 ≤ n ≤ 105) — количество чисел, которые мама подарила Пете. Во второй строке заданы сами числа через пробел. Все они целые, неотрицательные и не превосходят 1018.

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.

Выходные данные

Выведите n целых чисел через пробел, i-е из которых должно быть равно 1, если Петя оставляет себе i-е по порядку число из набора или 2, если Петя отдает соответствующее число Маше. Числа нумеруются в том же порядке, в котором они заданы во входных данных.

Примеры
Входные данные
6
1 2 3 4 5 6
Выходные данные
2 2 2 2 2 2
Входные данные
3
1000000000000 1000000000000 1000000000000
Выходные данные
2 2 2
Входные данные
8
1 1 2 2 3 3 4 4
Выходные данные
1 2 1 2 2 2 1 2