Гра в квадрати
У Васі та Петі є 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). Якщо виграє перший гравець, у другий рядок виведіть координати клітинки, яку на першому ході повинен вибрати перший гравець, щоб виграти. Якщо таких декілька, виведіть першу у лексикографічному порядку.