== 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ă 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ţă*.

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

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:

| Header necesar | - | - | import sys | - | 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 precizari

h2. Restricţii si precizări

* 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:

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