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

Poveste şi cerinţă...

Bulbuka a primit de curând cadou un infinit de tromino-uri  în formă de L. După ce s-a jucat un timp cu ele, a ajuns la următoarea concluzie: poate să acopere cu tromino-uri o tablă de dimensiuni {*2^K^ x 2^K^*} aproape complet (mai puţin un pătrăţel de dimensiune 1x1). Deşteapta de Bulbuka are un algoritm pentru asta: porneşte de la o configuraţie {*2^K-1^ x 2^K-1^*}, o copiază de încă 3 ori, apoi roteşte 2 dintre copii şi la sfârşit, adaugă un tromino la mijloc (v-a făcut un desen mai jos, ca să înţelegeţi mai bine, pentru {*K*} = 1, 2 şi 3). Pornind de la o configuraţie de acest tip, ea a observat că poate roti la 90o câte un tromino, în sensul acelor de ceasornic sau invers, doar dacă după rotire încape înapoi pe tablă. Folosind astfel de rotaţii, pătrăţelul lipsă poate ajunge pe orice poziţie de pe tablă.
Bulbuka vă pune acum {*Q*} întrebări de tipul: care este numărul minim de rotaţii necesare pentru ca pătrăţelul lipsă să ajungă de la coordonatele {*(S{~R~}, S{~C~})*} la coordonatele {*(F{~R~}, F{~C~})*}?
 
{! problema/tromino?tromino.png 100% !}
 
h2. Cerinţă
 
Pentru o configuraţie {*2^K^ x 2^K^*} , explicată  în enunţ, Bulbuka vă pune {*Q*} întrebări de tipul:  care este numărul minim de rotaţii de 90 grade de care avem nevoie pentru a aduce pătrăţelul lipsă din punctul {*(S{~R~}, S{~C~})*} în {*(F{~R~}, F{~C~})*}?

h2. Date de intrare

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

Fişierul de intrare $tromino.in$ conţine pe prima linie două valori {*K*} şi {*Q*}, unde {*2^K^ x 2^K^*}  reprezintă dimensiunea tablei şi {*Q*} reprezintă numărul de întrebări pe care le pune Bulbuka. Fiecare din următoarele {*Q*} linii din fişier reprezintă o întrebare şi conţine valorile {*S{~R~}, S{~C~}, F{~R~}, F{~C~}*} unde {*(S{~R~}, S{~C~})*} reprezintă coordonatele iniţiale ale pătrăţelului lipsă şi {*(F{~R~}, F{~C~})*} reprezintă coordonatele finale la care va ajunge pătrăţelul.

h2. Date de ieşire

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

Fişierul de ieşire $tromino.out$ va conţine {*Q*} linii, ce reprezintă răspunsurile la cele {*Q*} întrebări.

h2. Restricţii

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

* 1 ≤ {*K*} ≤ 60;
* 3 ≤ {*Q*} ≤ 5000;
* 0 ≤ {*S{~R~}, S{~C~}, F{~R~}, F{~C~}*} < {*2^K^*}
* Se garantează că pentru orice poziţie a pătrăţelului lipsă există o configuraţie unică a tablei
* Pentru 15% din teste {*K*} ≤ 3

h2. Exemplu
 
table(example). |_. tromino.in |_. tromino.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
h3. Explicaţie

h2. Exemplu

...

table(example). |_. tromino.in |_. tromino.out |_. Explicatie |
| 2 1
1 3 0 0
| 4
| {! problema/tromino?tromino2.png 74% !}
|
| 3 5
0 0 0 1
0 0 1 1
0 0 3 3
0 0 2 4
1 0 1 0
| 1
2
6
8
0
| .
|

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