Загадане дерево

Limits: 2 sec., 256 MiB

Ця задача інтерактивна. Подбайте про виклик методу flush після виводу кожного рядка.

Зеник з Марічкою пробують вгадати, що це за дерево перед ними. Дерево — це зв’язний граф з $n$ вершин та $n - 1$ ребер, де між кожною парою вершин існує єдиний простий шлях. Також кожне ребро має унікальну вагу $w_i$, тобто всі $w_i$ — різні.

Початково, Зеник та Марічка знають лише кількість вершин $n$. Далі за одну хвилину вони можуть обрати пару вершин $u$ та $v$ і визначити, яка ж вага найважчого ребра на шляху від $u$ до $v$. Всього вони можуть робити цю операцію не більше ніж 4477 разів. Після цього пара хоче знайти дерево, яке є схожим на оригінальне. Дерево називається схожим на оригінальне, якщо для будь-якої пари вершин $u$ і $v$ вага найважчого ребра на шляху між ними така ж, як в оригінальному.

Допоможіть Зенику та Марічці побудувати стратегію, щоб знайти схоже дерево.

Взаємодія

Спочатку вам слід прочитати одне ціле число $n$.

Далі, щоб задати питання, виведіть ? та два різні цілі числа $u$ та $v$ ($1 \le u, v \le n$, $u \ne v$). Після цього зчитайте рядок з відповіддю на запитання — вага найважчого ребра на шляху між $u$ та $v$. Ви можете задавати не більше ніж 4477 запитань.

Коли ви упевнені, що знаєте хоча б одне схоже дерево, виведіть !. Після цього в наступних $n-1$ рядках виведіть по 3 цілі числа $x_i$, $y_i$, $z_i$ — ребро між $x_i$ та $y_i$ вагою $z_i$. Повинні виконуватись обмеження $1 \le x_i, y_i \le n$, $1 \le z_i \le 10^9$.

Зауважте, що для кожного тесту дерево зафіксоване перед запитаннями від Зеника та Марічки, та не може змінюватись в процесі.

Constraints

$2 \le n \le 477$,

$1 \le u_i, v_i \le n$,

$1 \le w_i \le 10^9$,

усі $w_i$ різні.

Samples

Notes

Пари вершин, для яких знаходили відповідь Зеник та Марічка:

• Вершина 1 та 4 – найважче ребро ваги 17 між вершинами 4 та 7.

• Вершина 1 та 5 – найважче ребро ваги 7 між вершинами 1 та 7.

• Вершина 6 та 3 – найважче ребро ваги 5 між вершинами 2 та 3.

• Вершина 5 та 6 – найважче ребро ваги 7 між вершинами 1 та 7.

Далі Зеник та Марічка вгадують схоже дерево. Воно не повністю співпадає з оригінальним деревом, але для кожної пари вершин вага найважчого ребра на шляху така ж.