Двое играют в игру. Есть несколько кучек спичек. За один ход разрешается взять любое ненулевое количество спичек из любой кучки, кто не может сделать ход, тот проиграл. Определите, кто выигрывает при правильной игре.
Входные данные
В первой строке входного файла записано натуральное число N — количество кучек. Во второй строке записаны N целых чисел — количество спичек в кучках. Все числа во входном файле не превосходят 100000.
Выходные данные
Выведите «1», если выигрывает первый игрок или «2», если выигрывает второй игрок. Если выигрывает первый игрок, во второй строке выведите число K — общее количество выигрышных ходов. В последующие K строк выведите информацию о выигрышных ходах — пары чисел, перечисленные в порядке возрастания первой координаты, а при равенстве в порядке возрастания второй координаты. В каждой такой паре первое число должно обозначать номер кучки, а второе — количество спичек, которые необходимо взять из этой кучки.
|
Ввод |
Вывод |
1
10 |
1
1
1 10
|
2
1 1 |
2 |