Є ~N~ купок, кожна з яких містить деяку кількість паличок. Двоє грають у таку гру. Кожен з гравців на кожному своєму ході може забрати з будь-якої однієї купки будь-яку кількість паличок, від 1 до зразу всіх паличок цієї купки. Палички можна лише забирати (ні додавати, ні перекладувати з купки в купку не можна). Ніяких інших варіантів ходу нема. Коли купка стає порожньою (кількість паличок = 0), гра просто продовжується для решти купок. Ходять гравці по черзі, пропускати хід не можна. Виграє той, хто забирає останню паличку (можливо, разом із ще деякими) з останньої купки. (Інакше кажучи, виграє той, після чийого ходу не лишається жодної палички в жодній купці.)

Напишіть програму, яка визначатиме, хто виграє при правильній грі обох гравців. Іншими словами, хто може забезпечити собі виграш, хоч би як не грав інший. Якщо виграє перший, то програма повинна знайти також сукупність усіх його виграшних перших ходів.

Вхідні дані

Перший рядок містить єдине ціле число ~N~ (~1\leqslant N\leqslant 123~) — кількість купок. Другий рядок містить рівно ~N~ чисел ~k_1~, ~k_2~, ..., ~k_N~, розділених одинарними пропусками (пробілами) — початкові кількості паличок у кожній з купок. Всі числа ~k_1~, ~k_2~, ..., ~k_N~ є цілими, у межах від 1 до 123456, серед них можуть бути як однакові, так і різні.

Результати

Перший рядок має містити єдине ціле число, або 1 (якщо перший гравець може забезпечити собі виграш), або 2 (якщо другий). Якщо відповідь з першого рядка 2, то на цьому виведення слід припинити. А якщо відповідь з першого рядка 1, то далі треба вивести також перелік всіх можливих перших ходів першого гравця, після яких другий (при правильній грі першого) вже ніяк не зможе виграти. Цей перелік виводити в такому форматі: кожен такий хід в окремому рядку; кожен хід записується як пара чисел через пропуск: спочатку з якої купки слід забрати палички, потім скільки штук паличок треба забрати;якщо є багато різних виграшних перших ходів, вони повинні бути відсортовані за зростанням номера купки, а якщо є багато різних виграшних перших ходів, де палички беруться з однієї й тієї ж купки, то за зростанням кількості паличок, що беруться.

Кількість перших виграшних ходів виводити не треба. Вважати, що купки занумеровані з одиниці: 1, 2, ..., ~N~.

Приклади

Вхід

2
3 4

Результат

1
2 1

Вхід

2
5 5

Результат

2

Вхід

4
1 2 5 7

Результат

1
1 1
3 1
4 1

Примітка

В умові є одне дрібне неможливе й непотрібне уточнення. Приблизно у стилі «якщо ~2+2=5~, то виведіть слово "хрпщ"» - його виводити все'дно не доведеться, бо все'дно ~2+2\neq 5~. Знайти це дрібне неможливе й непотрібне уточнення – одне із завдань, які дуже бажано зробити у процесі розв'язування цієї задачі.