neuroni

Naisac, în tren spre lotul de la Julc, se gândește la un arbore cu $N$ noduri, în care fiecare nod este numerotat cu un număr între $1$ și $N$ (inclusiv). De asemenea, el vă garantează ca în acest arbore, fiecare nod are maxim 3 muchii atașate de el.

Naisac, pasionat și el de informatică, nu vă va spune direct care este arborele. În schimb, pentru a îl putea afla, el vă va răspunde doar la întrebări care îi fac pe plac.

Protocol de interacțiune

Voi îl puteți întreba afișând pe o linie folosind std::cout (urmat de std::cout << std::endl):

$\text{\texttt{? a b c }}$

(cu $1 \leq a, b, c \leq N$).

El va răspunde la întrebarea: "Este $dist(a, c) + dist(c, b) = dist(a, b)$?" cu 0 sau 1, 0 reprezentând fals și 1 adevărat. Altfel văzut, el va răspunde la întrebarea "Este nodul $c$ pe drumul cel mai scurt de la $a$ la $b$?".

(Naisac poate răspunde și -1, dacă ați pus o întrebare invalidă sau ați depășit limita de întrebări. În acest caz, programul vostru trebuie să se oprească imediat pentru a primi Wrong Answer, altfel riscați Time Limit Exceeded).

Când sunteți siguri că știți care este arborele secret al lui Naisac, puteți afișa pe o linie folosind std::cout (urmat de std::cout << std::endl):

$\text{\texttt{!}} u_1 \text{ } v_1 \text{ } u_2 \text{ } v_2 \ldots u_{N-1} \text{ }v_{N-1}$

unde $(u_1, v_1), (u_2, v_2), \ldots, (u_{N - 1}, v_{N - 1})$ reprezintă muchiile arborelui determinat. Evident, toate muchiile afișate trebuie să fie distincte, și mai mult $u_i \neq v_i$.

Aici se termină interacțiunea, și Naisac vă va da un număr între 0 și 100 de puncte dacă ați ghicit corect sau nu arborele, și în funcție de cât de puține întrebări ați pus.

Date de intrare

Pe prima linie, veți primi numărul $N$.
Apoi, pentru fiecare întrebare pe care o puneți, veți primi pe o linie nouă răspunsul (-1, 0 sau 1).

Date de ieșire

Puteți afișa pe fiecare linie fie:

• "$?$ $a$ $b$ $c$" pentru a pune o întrebare.
• "$!$ $u_1$ $v_1$ $\dots$" pentru a ghici arborele.

Restricții

• $1 \leq N \leq 10^4$
• Dacă puneți mai mult de $5 \cdot 10^6$ întrebări, automat luați 0 puncte.
• $1 \leq a, b, c \leq N$
• $1 \leq u_i, v_i \leq N$
• Muchiile arborelui aflat și capetele acestora se pot afișa în orice ordine
• $dist(p, q)$ este numărul de muchii care se află pe cel mai scurt drum de la nodul $p$ la nodul $q$ care parcurge doar muchiile și nodurile arborelui
• Naisac nu răspunde la alte tipuri de întrebări despre arbore, dar s-ar putea să răspundă dacă îl întrebați despre snacksuri

Punctare

Dacă ați identificat corect toate muchiile arborelui, punctajul pe care îl veți primi pe test va fi calculat în funcție de numărul de întrebări $Q$ pe care le-ați pus. Fie raportul $R = \frac{Q}{N \log_2 N}$.

• Dacă $N \leq 2$ sau $R \leq 2.8$, veți primi 100% din punctajul alocat testului.
• Dacă $R > 2.8$, procentajul din punctaj se calculează după următoarea formulă: $P(Q) = 100 \cdot \left( 0.4 + 0.6 \cdot 0.1^{R - 2.8} \right)$

Notă: Orice soluție care identifică arborele corect, indiferent de numărul de întrebări (atâta timp cât se respectă limita de $5 \cdot 10^6$ întrebări), are asigurat un punctaj de bază de $40\%$ din punctajul testului.

Exemple

Explicație

Arborele ascuns la care s-a gândit Gigel are $N = 4$ noduri și următoarele muchii: $(1, 2), (2, 3), (2, 4)$. Structura este validă deoarece nodul 2 are gradul 3, iar celelalte au gradul 1.

• La prima întrebare (? 1 3 2), concurentul întreabă dacă nodul $2$ se află pe drumul de la $1$ la $3$. Cum drumul este $1 \rightarrow 2 \rightarrow 3$, răspunsul lui Naisac este 1 (Adevărat).
• La a doua întrebare (? 1 4 3), concurentul întreabă dacă nodul 3 se află pe drumul de la 1 la 4 ($1 \rightarrow 2 \rightarrow 4$). Răspunsul este 0 (Fals).
• La a treia întrebare (? 3 4 2), concurentul întreabă dacă nodul 2 se află pe drumul de la 3 la 4 ($3 \rightarrow 2 \rightarrow 4$). Răspunsul este 1 (Adevărat).

În urma acestor deducții, concurentul a reușit să reconstituie arborele și afișează cele 3 muchii găsite: ! 1 2 2 3 2 4. (Ordinea muchiilor sau ordinea capetelor în cadrul unei muchii afișate nu contează).