Игра в квадраты
У Васи и Пети есть k-мерный клетчатый параллелепипед размером n_1×n_2×...×n_k. Они ходят по очереди. За ход игрок выбирает один из параллелепипедов, лежащих на столе. В нем игрок выбирает любую клетку и разрезает параллелепипед вдоль его сторон через эту клетку, и клетки, попавшие на разрез, удаляются. Образуется несколько кусков. При этом размеры хотя бы одного из кусков должны быть попарно взаимно просты с соответствующими размерами исходного куска. Кто не может сделать ход, проигрывает. Ваша задача - выяснить, кто выиграет при правильной игре.
Например, пусть k=2 и на столе есть кусок 6×5. Тогда, выбрав клетку (1, 4), получатся куски размерами 5×1 и 5×3. При этом размеры куска 1×5 попарно взаимно просты с размерами исходного 6×5. Если же выбрать клетку (3, 2), то получится четыре куска: 2×1, 3×1, 2×3, 3×3. При этом ни один из них не удовлетворяет условию попарной взаимной простоты (например, у куска 3×2первый размер 3 не взаимно прост с первым размером исходного - 6).
Входные данные
В первой строке число k, во второй строке n_1, n_2, ..., n_k. 1 ≤ k ≤ 8, 1 ≤ (n_1+1)×(n_2+1)×...×(n_k+1) ≤ 10000.
Выходные данные
В первую строку выведите номер выигрывающего игрока (1 или 2). Если выиграет первый игрок, во вторую строку выведите координаты клетки, которую на первом ходу должен выбрать первый игрок, чтобы выиграть. Если таких несколько, выведите первую в лексикографическом порядке.