Центральний елемент
Це інтерактивна задача.
У вас є перестановка P чисел від 1 до n, яка вам невідома, P = <P_1, P_2, …, P_n>. Ви можете ставити такі запитання: для трьох різних позицій i, j та k, яке з чисел P_i, P_j та P_k є середнім? Елемент є середнім, якщо він не є ні найменшим, ні найбільшим.
Наприклад, якщо перестановка <2, 1, 4, 3>, і ви запитаєте про позиції 1, 2 та 3, ви отримаєте 2, тому що 2 є середнім елементом множини {P_1, P_2, P_3} = {2, 1, 4}. Зверніть увагу, що ви не отримуєте інформацію про те, на якій саме позиції серед 1, 2 та 3 вона знаходиться.
Ваше завдання - знайти перестановку P. Насправді, для кожної перестановки P існує множина S(P) перестановок, які не можна відрізнити від P за допомогою дозволених запитань. Ви повинні знайти будь-яку перестановку з цієї множини.
Вхідні дані
Перший рядок стандартного вводу містить n, розмір перестановки (3 <= n <= 200).
Кожен з наступних рядків стандартного вводу містить відповідь на ваше питання - число, яке є середнім серед чисел на запитаних позиціях.
Протокол взаємодії
Спочатку ваша програма повинна прочитати з стандартного вводу одне ціле число n, яке є розміром перестановки.
Програма повинна записати в стандартний вихід один рядок з трьома позиціями, про які ви запитуєте, і чекати рядок у стандартному вводі з відповіддю, потім записати наступне питання і прочитати наступну відповідь, і так далі, поки ви не дізнаєтеся перестановку P до S(P).
Як тільки ви дізнаєтеся відповідь, виведіть один рядок зі словом "OK" і перестановкою P.
Вихідні дані
Коли ви задаєте питання, кожен рядок стандартного виходу повинен містити три різні цілі числа з діапазону від 1 до n, розділені пробілами. Ви можете задати не більше 2000 питань.
Коли ви надаєте відповідь, рядок стандартного виходу повинен містити слово "OK", і числа P_1, P_2, …, P_n, всі розділені пробілами. Після виведення цього рядка ваша програма повинна завершити роботу.
Ви повинні очистити стандартний вихід після виведення кожного рядка.