У Васи и Пети есть \textbf{k}-мерный клетчатый параллелепипед размером \textbf{n_1}×\textbf{n_2}×...×\textbf{n_k}. Они ходят по очереди. За ход игрок выбирает один из параллелепипедов, лежащих на столе. В нем игрок выбирает любую клетку и разрезает параллелепипед вдоль его сторон через эту клетку, и клетки, попавшие на разрез, удаляются. Образуется несколько кусков. При этом размеры хотя бы одного из кусков должны быть попарно взаимно просты с соответствующими размерами исходного куска. Кто не может сделать ход, проигрывает. Ваша задача - выяснить, кто выиграет при правильной игре. \includegraphics{https://static.e-olymp.com/content/0a/0afeecde551414cc22d9b124a7823da2fe0376e9.jpg} Например, пусть \textbf{k=2} и на столе есть кусок \textbf{6}×\textbf{5}. Тогда, выбрав клетку (\textbf{1}, \textbf{4}), получатся куски размерами \textbf{5}×\textbf{1} и \textbf{5}×\textbf{3}. При этом размеры куска \textbf{1}×\textbf{5} попарно взаимно просты с размерами исходного \textbf{6}×\textbf{5}. Если же выбрать клетку (\textbf{3}, \textbf{2}), то получится четыре куска: \textbf{2}×\textbf{1}, \textbf{3}×\textbf{1}, \textbf{2}×\textbf{3}, \textbf{3}×\textbf{3}. При этом ни один из них не удовлетворяет условию попарной взаимной простоты (например, у куска \textbf{3}×\textbf{2} первый размер \textbf{3} не взаимно прост с первым размером исходного - \textbf{6}). \InputFile В первой строке число \textbf{k}, во второй строке \textbf{n_1}, \textbf{n_2}, ..., \textbf{n_k}. \textbf{1} ≤ \textbf{k} ≤ \textbf{8}, \textbf{1} ≤ \textbf{(n_1+1)}×\textbf{(n_2+1)}×...×\textbf{(n_k+1)} ≤ \textbf{10000}. \OutputFile В первую строку выведите номер выигрывающего игрока (\textbf{1} или \textbf{2}). Если выиграет первый игрок, во вторую строку выведите координаты клетки, которую на первом ходу должен выбрать первый игрок, чтобы выиграть. Если таких несколько, выведите первую в лексикографическом порядке.