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

Обмеження: 2 сек., 256 МіБ

Ця задача інтерактивна. Подбайте про виклик методу 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\).

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

Обмеження

\(2 \le n \le 477\),

\(1 \le u_i, v_i \le n\),

\(1 \le w_i \le 10^9\),

усі \(w_i\) різні.

Приклади

Примітки

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

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

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

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

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

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