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

Perry a ajuns la Doofenshmirtz pentru a-l impiedica din a distruge intreaga lume cu noul sau inator.
Totusi, odata ce intra pe usa are o surpriza: in loc de sala mare, obisnuita, se afla intr un hol cu N placute, numerotate de la 1 la N, el aflandu-se la intrare, *nefiind momentan pe nicio placuta*.
Robotul Norm, asistentul lui Doofenshmirtz ii zice apoi agentului P: "_Te afli cea mai noua capcana anti-ornitorinci. Tot ce trebuie sa faci ca sa scapi este sa ajungi la finalul holului. Totusi, sub K dintre placute se afla bombe, am fi pus sub toate, dar nu ne-a permis bugetul, deci daca vei calca pe o placuta care are sub ea o bomba, vei muri pe loc. Bafta sa evadezi si de data asta!_"

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ă î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$.

Ca intotdeauna, Perry este pregatit. Are un dispozitiv in care poate scrie, de mai multe ori, cate un triplet (c , a , b), iar dispozitivul ii va returna 1 daca in secventele de placute de lungime c care incep pe a, respeciv b sunt un numar egal de placute periculoase (cu bombe sub), sau 0 altfel.

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!_"

Evident, Perry trebuie sa afle pozitiile placutelor periculoase. Voi trebuie sa il ajutati folosindu-va de dispozitivul lui, incercand sa introduceti in el cat mai putine triplete (nu putem pierde prea mult timp, pentru ca altfel nu il vom opri pe Doofenshmirtz inainte sa isi realizeze planurile malefice).

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.

h2. Interactiune

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).

Initial se citesc din _stdin_ numerele N si K.
Programul vostru are voie sa puna query-uri scriind in _standard output_:

h2. Interacţiune

* "? c a b" reprezentand introducerea unui triplet de numere in dispozitiv.

Iniţial se citesc din _stdin_ numerele $N$ şi $K$.
Programul vostru are voie să pună query-uri scriind în _standard output_:

Dupa fiecare astfel de query, interactorul va va raspunde in _stdin_ astfel:

* "? c a b" reprezentând introducerea unui triplet de numere in dispozitiv.

* "0" : daca in secventele de lungime c care incep in a, respectiv b *nu* se gasesc acelasi numar de placute periculoase.

După fiecare astfel de query, interactorul vă va răspunde in _stdin_ astfel:

* "1" : daca in secventele de lungime c care incep in a, respectiv b se gasesc acelasi numar de placute 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ă 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*, daca 1 ≤ c ≤ N si daca 1 ≤ a , b , a + c - 1 , b + c - 1 ≤ N

* $"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.

Dupa ce ati aflat pozitiile placutelor care au bombe sub ele, afisati "! p1 p2 ... pk", unde pi = pozitia placutei periculoase cu numarul i, iar apoi terminati programul.

* $"-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ă 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

h2. Restricţii si precizari
 
* 1 ≤ N ≤ 10^9^
* 1 ≤ K ≤ 50
* K * 2 + 1 ≤ N
 
Fie Q numarul de query-uri pe care le faceti la un test. Punctajele partiale se vor acorda in felul urmator:
 
* 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") ==