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 2Kx2K 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 2K-1x2K-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 (SR,SC) la coordonatele (FR,FC)?

Cerința

Pentru o configuraţie 2Kx2K, explicată în enunţ, Bulbuka vă pune Q întrebări de tipul: care este numărul minim de rotaţii de 90o de care avem nevoie pentru a aduce pătrăţelul lipsă din punctul (SR,SC) în (FR,FC)?

Date de intrare

Fișierul de intrare tromino.in conține pe prima linie două valori K şi Q, unde 2Kx2K 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 SR, SC, FR, FC unde (SR,SC) reprezintă coordonatele iniţiale ale pătrăţelului lipsă şi (FR,FC) reprezintă coordonatele finale la care va ajunge pătrăţelul.

Date de ieșire

Fișierul de ieșire tromino.out va conține Q linii, ce reprezintă răspunsurile la cele Q întrebări.

Restricții și precizări

• 1 ≤ K ≤ 60; 3 ≤ Q ≤ 5000; 0 ≤ SR, SC, FR, FC < 2K
• 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

Exemplul 1

tromino.in

2 1
1 3 0 0

tromino.out

4

Explicație

Exemplul 2

tromino.in

3 5
0 0 0 1
0 0 1 1
0 0 3 3
0 0 2 4
1 0 1 0

tromino.out

1
2
6
8
0