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

Poveste şi cerinţă...

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

h2. Date de intrare

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

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

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. Date de ieşire

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

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

h2. Interacţiune

h2. Restricţii

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

table(example). |_. capcana.in |_. capcana.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

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") ==