majoritar

Comisia a ascuns un șir $A$ format din $N$ numere naturale. Se garantează că șirul admite un element majoritar (un element care apare de strict mai mult de $\lfloor N / 2 \rfloor$ ori în șir).

Fiindcă elementul majoritar din șirul inițial este prea evident, Comisia vă cere să aflați un indice (o poziție) la care se află acesta, cât și frecvența cu care el apare în șirul ascuns $A$. Pentru a face asta, puteți interacționa cu programul comisiei. La o întrebare, puteți alege un subșir de indici și puteți întreba dacă elementele de la acele poziții admit, la rândul lor, un element majoritar sau nu.

Protocol de interacțiune

Puteți pune întrebări afișând pe o linie folosind std::cout (urmat de std::cout << std::endl):

$\text{\texttt{? K }} i_1 \text{ } i_2 \dots i_K$

Aici $K$ ($1 \leq K \leq N$) reprezintă numărul de indici interogați, iar $i_1, i_2 \dots i_K$ ($1 \leq i_j \leq N$) trebuie să fie indici distincți.

Pentru fiecare întrebare, Comisia va răspunde la intrarea standard cu un număr pe o linie nouă:

• 1: Elementele aflate la indicii interogați admit un element majoritar.
• 0: Elementele aflate la indicii interogați nu admit un element majoritar.
• -1: Ați pus o întrebare invalidă, ați interogat aceiași indici de mai multe ori într-un query, sau ați depășit limita maximă absolută 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 de răspuns, trebuie să afișați pe o linie folosind std::cout (urmat de std::cout << std::endl):

$\texttt{! I F}$

unde $I$ reprezintă un indice (orice valoare validă între $1$ și $N$) la care se află elementul majoritar, iar $F$ reprezintă frecvența (numărul de apariții) acestuia în șirul inițial $A$. Aici se termină interacțiunea.

Punctare

Fie $Q$ numărul de întrebări de tip ? puse de programul vostru.

Dacă interacțiunea este invalidă sau programul nu afișează un răspuns corect, punctajul pe test este 0.

În caz contrar, punctajul pe un test se acordă astfel:

• Dacă $Q \leq N + 50$, veți primi 100% din punctajul testului.
• Dacă $N + 50 < Q \leq 2N + 50$, punctajul este $100\% - 40\% \cdot \frac{Q - (N + 50)}{N}.$
• Dacă $2N + 50 < Q \leq N \cdot \lceil \log_2 N \rceil + 50$, veți primi 40% din punctajul testului.
• Dacă $Q > N \cdot \lceil \log_2 N \rceil + 50$, dar programul afișează răspunsul corect în limita de timp, veți primi 20% din punctajul testului.

Date de intrare și ieșire

Pe prima linie a datelor de intrare veți primi numărul $N$. Apoi, programul vostru trebuie să citească răspunsurile pentru fiecare întrebare pusă. Toate întrebările se vor afișa la datele de ieșire, respectând formatul precizat în secțiunea Protocol de interacțiune. Nu uitați să afișați la final răspunsul sub forma ! I F.

Restricții

• $1 \leq N \leq 10 \ 000$
• NU se garantează evaluarea în limita de timp a soluției dacă numărul total de elemente interogate este mai mare decât $4 \cdot 10^5$.

Exemple