Питер Паркер планирует сыграть с Доктором Октопусом в игру о циклах. Циклом называется последовательность вершин, такая что первая вершина соединена со второй, вторая — с третьей и так далее, а последняя, в свою очередь, соединена с первой. Цикл может состоять и из одной изолированной вершины.
В начале игры имеются k циклов, i-й из которых состоит ровно из vi вершин. Игроки ходят по очереди, Питер ходит первым. За один ход игрок должен выбрать какой-нибудь цикл, состоящий хотя бы из 2 вершин (обозначим размер выбранного цикла за x), и заменить его двумя непустыми циклами размера p и x - p для некоторого 1 ≤ p < x, выбор которого остаётся на усмотрение игрока. Игрок, который не может сделать ход, проигрывает (и расстаётся с жизнью!).
Питер хочет протестировать несколько изначальных конфигураций игры, перед тем как вступить в схватку с Доктором Октопусом. Изначально набор циклов пуст. Перед i-м тестом Питер добавляет в набор цикл, состоящий из ai вершин (обратите внимание: набор является мультимножеством, то есть может содержать несколько циклов одинакового размера). После добавления каждого цикла Питер хочет знать, кто выигрывает на текущем наборе?
Питер вообще неплохо разбирается в математике, но сейчас решил обратиться к вам за помощью.
Выходные данные
Выведите результаты всех тестов в порядке, в котором они проводятся. Выводите 1, если при оптимальной игре победит игрок, который ходит первым, и 2 в противном случае.
Примечание
Рассмотрим первый пример:
В первом тесте Питера есть только один цикл, состоящий из 1 вершины, поэтому первый игрок не может сделать ход и проигрывает.
Во втором тесте есть один цикл длины 1 и один цикл длины 2. Первый игрок делит второй цикл на два цикла длины 1, после чего второй игрок не может сделать ход и проигрывает.
В третьем тесте имеются циклы размера 1, 2 и 3. Первый игрок может поделить последний цикл на циклы длины 1 и 2, после чего останется набор 1, 1, 2, 2, в котором можно сделать ровно два хода — делить циклы длины 2 на два цикла длины 1. Таким образом, оба игрока сделают по одному ходу, и второй проиграет.
Рассмотрим второй тестовый пример:
Циклы длины 1 бесполезны, потому что с ними никогда нельзя сделать ход, поэтому можно считать, что их просто нет.
Когда появляется цикл длины 5, у первого игрока есть два варианта хода: поделить его на 1 и 4 или на 2 и 3.
- Если поделить на циклы длины 1 и 4, то своим ходом второй игрок поделит 4 на два цикла длины 2, после чего останется два однозначно определяемых хода.
- Если поделить на циклы длины 2 и 3, то второй игрок поделит цикл длины 3 на 2 и 1, опять оставив ситуацию когда есть два однозначных хода.
Таким образом, второй игрок может гарантировать себе победу во всех тестах второго примера.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 2 3
|
2
1
1
|
|
2
|
5
1 1 5 1 1
|
2
2
2
2
2
|