Маленький Петя очень любит числа. Недавно мама подарила ему набор из n целых неотрицательных чисел. Больше чем числа Петя любит только играть с маленькой Машей. Он тут же решил поделиться с ней частью своего нового набора. Чтобы вместе детям было еще веселее играть, Петя решил отдать Маше такой набор чисел, для которого выполняются следующие условия:
- Обозначим через x1 xor всех чисел, которые остались у Пети, а через x2 — xor всех чисел, которые он отдал Маше. Значение (x1 + x2) должно быть как можно больше.
- Если существует несколько способов разделить набор чисел так, чтобы предыдущее условие выполнялось, то Петя минимизирует значение x1.
Под операцией xor подразумевается побитовое исключающее «ИЛИ», которое обозначается как «xor» в языке Pascal и «^» в C/C++/Java.
Помогите Пете разделить набор требуемым образом. Если существует несколько подходящих разбиений, найдите любое. Обратите внимание, что после того, как Петя отдаст часть своих чисел Маше, у него их может не остаться вовсе. Возможна и обратная ситуация, когда Петя ничего не отдает Маше. В обоих случаях следует считать, что xor пустого набора чисел равен 0.
Выходные данные
Выведите n целых чисел через пробел, i-е из которых должно быть равно 1, если Петя оставляет себе i-е по порядку число из набора или 2, если Петя отдает соответствующее число Маше. Числа нумеруются в том же порядке, в котором они заданы во входных данных.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
1 2 3 4 5 6
|
2 2 2 2 2 2
|
|
2
|
3
1000000000000 1000000000000 1000000000000
|
2 2 2
|
|
3
|
8
1 1 2 2 3 3 4 4
|
1 2 1 2 2 2 1 2
|