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

Poveste şi cerinţă...

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

h2. Date de intrare

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

Fişierul de intrare $capcana.in$ ...

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.

h2. Date de ieşire

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

În fişierul de ieşire $capcana.out$ ...

h2. Interactiune

h2. Restricţii

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

* $... ≤ ... ≤ ...$

* "? c a b" reprezentand introducerea unui triplet de numere in dispozitiv.
 
Dupa fiecare astfel de query, interactorul va va raspunde in _stdin_ astfel:
 
* "0" : daca in secventele de lungime c care incep in a, respectiv b *nu* se gasesc acelasi numar de placute periculoase.
 
* "1" : daca in secventele de lungime c care incep in a, respectiv b se gasesc acelasi numar de placute 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
 
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.
 
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}; |
| Functie | fflush(stdout) sau cout.flush() | flush(output) | sys.stdout.flush() | System.out.flush() | io::stdout().flush().unwrap(); |
 
 
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

h2. Exemplu

table(example). |_. capcana.in |_. capcana.out |

table(example). |_. stdin |_. stdout |

| This is some
  text written on
  multiple lines.