Perry a ajuns la Doofenshmirtz pentru a-l împiedica din a distruge întreaga lume cu noul său inator.

Totuşi, odata ce intră pe uşă are o surpriză: în loc de sala mare, obişnuită, se află intr-un hol cu podeaua acoperită cu N plăcuţe, numerotate de la 1 la N, el aflându-se la intrare, *nefiind momentan pe nicio plăcuţă*.

Totuşi, odata ce intră pe uşă are o surpriză: în loc de sala mare, obişnuită, se află într-un hol cu podeaua acoperită cu $N$ plăcuţe aşezate în linie, numerotate de la $1$ la $N$, el aflându-se la intrare, fix *în spatele* plăcuţei $1$.

Robotul Norm, asistentul lui Doofenshmirtz îi zice apoi agentului P: "_Te afli în cea mai noua capcană anti-ornitorinci. Tot ce trebuie să faci ca să scapi este să ajungi la finalul holului. Totuşi, sub K dintre plăcuţe se află bombe. Am fi pus sub toate, dar nu ne-a permis bugetul, deci dacă vei călca pe o plăcuţă care are sub ea o bombă, vei muri pe loc. Baftă să evadezi şi de data asta!_"

Robotul Norm, asistentul lui Doofenshmirtz îi zice apoi agentului P: "_Te afli în cea mai noua "capcană":https://www.youtube.com/watch?v=zHNy4ztdn7w anti-ornitorinci. Tot ce trebuie să faci ca să scapi este să ajungi la finalul holului, să treci de plăcuţa $N$. Totuşi, sub $K$ dintre plăcuţe se află bombe. Am fi pus sub toate, dar nu ne-a permis bugetul, deci dacă vei călca pe o plăcuţă care are sub ea o bombă, vei muri pe loc. Baftă să evadezi şi de data asta!_"

Ca întotdeauna, Perry este pregătit. Are un dispozitiv în care poate scrie, de mai multe ori, câte un triplet (c , a , b), iar dispozitivul îi va returna 1 dacă in secvenţele de plăcuţe de lungime c care încep pe a, respectiv b sunt un număr egal de plăcuţe periculoase (cu bombe sub), sau 0 altfel.

Ca întotdeauna, Perry este pregătit. Are un dispozitiv în care poate scrie, de mai multe ori, câte un triplet $(c, a, b)$, iar dispozitivul îi va returna $1$ dacă in secvenţele de plăcuţe de lungime c care încep pe a, respectiv b sunt un număr egal de plăcuţe periculoase (cu bombe sub), sau $0$ altfel.

Evident, Perry trebuie să afle poziţiile plăcuţelor periculoase. Voi trebuie să îl ajutaţi folosindu-vă de dispozitivul lui, încercând să introduceţi în el cât mai puţine triplete (nu putem pierde prea mult timp, pentru că altfel nu îl vom opri pe Doofenshmirtz înainte să işi realizeze planurile malefice).
h2. Interacţiune

Iniţial se citesc din _stdin_ numerele N şi K.

Iniţial se citesc din _stdin_ numerele $N$ şi $K$.

Programul vostru are voie să pună query-uri scriind în _standard output_:
* "? c a b" reprezentând introducerea unui triplet de numere in dispozitiv.
După fiecare astfel de query, interactorul vă va răspunde in _stdin_ astfel:

* "0" : dacă in secvenţele de lungime c care încep in a, respectiv b *nu* se găsesc acelaşi număr de plăcuţe periculoase.

* $"0"$ : dacă in secvenţele de lungime c care încep in a, respectiv b *nu* se găsesc acelaşi număr de plăcuţe periculoase.

* "1" : dacă in secvenţele de lungime c care încep in a, respectiv b se găsesc acelaşi număr de plăcuţe periculoase.

* $"1"$ : dacă in secvenţele de lungime c care încep in a, respectiv b se găsesc acelaşi număr de plăcuţe periculoase.

* "-1" : dacă query-ul este invalid, trebuie să închideţi programul după ce primiţi acest verdict. Un query este considerat valid dacă intervalele (a , a + c - 1) si (b , b + c - 1) sunt *disjuncte*, dacă 1 ≤ c ≤ N şi dacă 1 ≤ a , b , a + c - 1 , b + c - 1 ≤ N

* $"-1"$ : dacă query-ul este invalid, trebuie să închideţi programul după ce primiţi acest verdict. Un query este considerat valid dacă intervalele $(a, a + c - 1)$ si $(b, b + c - 1)$ sunt *disjuncte*, dacă $1 ≤ c ≤ N$ şi dacă $1 ≤ a, b, a + c - 1, b + c - 1 ≤ N$

După ce aţi aflat poziţiile plăcuţelor care au bombe sub ele, afişati "! p ~1~  p ~2~  ... p ~K~ ", unde p ~i~ = poziţia plăcuţei periculoase cu numărul i, iar apoi terminaţi programul.

După ce aţi aflat poziţiile plăcuţelor care au bombe sub ele, afişati $"! p ~1~  p ~2~  ... p ~K~ "$, unde p ~i~ = poziţia plăcuţei periculoase cu numărul i, iar apoi terminaţi programul.

După fiecare query, inclusiv cel final trebuie să afişaţi '\n' şi să daţi flush la _standard output_. Pentru a da flush vă puteţi folosi de următorul tabel:
|_. Limbaj |_. C/C++ |_. Pascal |_. Python |_. Java |_. Rust |

| Header necesar | - | - | import sys | - | use std::io::{self,Write}; |

| Header necesar | 0 | 0 | import sys | 0 | use std::io::{self,Write}; |

| Functie | fflush(stdout) sau cout.flush() | flush(output) | sys.stdout.flush() | System.out.flush() | io::stdout().flush().unwrap(); |
h2. Restricţii si precizări

* 1 ≤ N ≤ 10^9^
* 1 ≤ K ≤ 50
* K * 2 + 1 ≤ N
 
Fie Q numărul de query-uri pe care le faceţi la un test. Punctajele parţiale se vor acorda in felul următor:
 
* 20 de puncte: N, Q ≤ 10^2^
* 30 de puncte Q ≤ 2K + 1 + log ~2~ N + (log ~2~ N + 2) * K * 2
* 50 de puncte Q ≤ 2K + 1 + log ~2~ N + (log ~2~ N + 2) * K

* $1 ≤ N ≤ 10^9^$
* $1 ≤ K ≤ 250$
* $K * 2 + 1 ≤ N$
* Pentru $20%$ din teste, $1 ≤ N ≤ 2000$
* Pentru încă $20%$ din teste, $K = 1$
* Placuţele capcană sunt fixate de dinainte. (Graderul nu este adaptiv)
 
h2. Punctare
 
Dacă setul poziţiilor plăcuţelor periculoase găsit de voi este diferit de cel corect, punctajul obţinut pe acel test va fi $0$ puncte.
Altfel, punctajul vostru va fi decis în funcţie de Q numărul de query-uri făcute:
 
* $50%$ din punctajul pe test pentru $Q ≤ 2 * (K + 1) * ( log ~2~ N + 4 )$
* $100%$ din punctajul pe test pentru $Q ≤ (K + 1) * ( log ~2~ N + 4 )$
* *In plus* pentru $1 ≤ N ≤ 2000$, punctajul pe test va fi acordat în totalitate dacă răspunsul este cel corect, atata timp cat $Q ≤ 10^4$

h2. Exemplu

table(example). |_. stdin |_. stdout |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

table(example). |_. stdin |_. stdout |_. Explicaţie |
| 3 1 | 0 | Se citesc N si K |
| 0 | ? 1 1 3 | Query compari plăcuţa 1 si plăcuţa 3|
| 1 | 0 | Se răspunde că plăcuţele sunt la fel|
| 0 | ! 2 | Plăcuţa 2 este singura care este periculoasă |

h3. Explicaţie

...

Din cele 3 plăcuţe, doar una este periculoasă. Când aflăm ca plăcuţa 1 si plăcuţa 3 sunt identice, devine clar faptul că niciuna dintre cele două nu pot avea o bombă sub, deoarece $K = 1$. Astfel putem trage concluzia că plăcuţa 2 este cea periculoasă.

== include(page="template/taskfooter" task_id="capcana") ==