h1. Z-parcurgere

Petrica are o tabla patratica de dimensiuni **2^n^*2^n^**. Ar vrea sa scrie pe patratelele tablei numere naturale cuprinse intre *1* si **2^n^*2^n^** conform unei parcurgeri mai deosebite pe care o numeste Z-parcurgere. O Z-parcurgere viziteaza recursiv cele patru cadrane ale tablei in ordinea: stanga-sus, dreapta-sus, stanga-jos, dreapta-jos. De exemplu, daca *n=1*, ordinea vizitarii patratelelor de pe tabla este in forma de Z, ca in figura urmatoare:

Petrica are o tabla patratica de dimensiuni **2^n^*2^n^**. Ar vrea sa scrie pe patratelele tablei numere naturale cuprinse intre 1 si **2^n^*2^n^** conform unei parcurgeri mai deosebite pe care o numeste Z-parcurgere. O Z-parcurgere viziteaza recursiv cele patru cadrane ale tablei in ordinea: stanga-sus, dreapta-sus, stanga-jos, dreapta-jos. De exemplu, daca *n=1*, ordinea vizitarii patratelelor de pe tabla este in forma de Z, ca in figura urmatoare:

|=. 1|=. 2|
|=. 3|=. 4|

|1|2|
 
|3|4|

Daca *n=2*, Petrica va traversa patratelele in ordinea:

|=.1 |=.2 |=. 5|=. 6|
|=. 3|=. 4|=. 7|=. 8|
|=. 9|=. 10|=. 13|=. 14|
|=. 11|=. 12|=. 15|=. 16|

|=.1|=.2|=. 5|6|
 
|=.3|=.4|=.7|=.8|
|=.9|=.10|=.13|=.14|
|=.11|=.12|=.15|=.16|

h2. Cerinta

La un moment dat Petrica ar vrea sa stie ce numar de ordine trebuie sa scrie conform Z-parcurgerii pe anumite patratele date prin coordonatele lor ( _x_, _y_ ). Petrica incepe umplerea tablei intotdeauna din coltul din stanga-sus.

La un moment dat Petrica ar vrea sa stie ce numar de ordine trebuie sa scrie conform Z-parcurgerii pe anumite patratele date prin coordonatele lor ( x, y ). Petrica incepe umplerea tablei intotdeauna din coltul din stanga-sus.

h2. Date de intrare

h2. Date de Intrare

Pe prima linie a fisierului de intrare **z.in** se afla doua numere naturale **N** si **K**, unde **N** reprezinta faptul ca tabla are dimensiunea **2^n^*2^n^**, iar *K* este numarul patratelelor pe care Petrica ar vrea sa stie ce numar va trebui sa scrie pe ele. Pe fiecare din urmatoarele **K** linii se afla cate doua numere naturale ( _x_, _y_ ), care reprezinta linia, respectiv coloana unui patratel ales. A _i+1_-a linie descrie al _i_-lea patratel ( i = 1, 2, ..., k ).

Pe prima linie a fisierului de intrare z.in se afla doua numere naturale N si K , unde N reprezinta faptul ca tabla are dimensiunea 2^n*2^n , iar K este numarul patratelelor pe care Petrica ar vrea sa stie ce numar va trebui sa scrie pe ele. Pe fiecare din urmatoarele K linii se afla cate doua numere naturale ( x, y ), care reprezinta linia, respectiv coloana unui patratel ales. A i+1 -a linie descrie al i -lea patratel ( i = 1, 2, ..., k ).

h2. Date de iesire

h2. Date de Iesire

Pe cele **K** linii ale fisierului de iesire **z.out** se va scrie cate un numar natural, corespunzator numarului pe care Petrica il va scrie pe patratelul ales. A _i_-a linie descrie al _i_ -lea patratel ( i = 1, 2, ..., k ).

Pe cele k linii ale fisierului de iesire z.out se va scrie cate un numar natural, corespunzator numarului pe care Petrica il va scrie pe patratelul ales. A i -a linie descrie al i -lea patratel ( i = 1, 2, ..., k ).

h2. Restrictii si precizari

* 1 <= **N** <= 15

. 1 <= N <= 15

* 1 <= **K** <= 1.000

. 1 <= K <= 1.000

* 1 <= _x_, _y_ <= 2^n^

. 1 <= x,y <= 2^n

h2. Exemplu

|**z.in**|**z.out**|

|z.in |z.out |

|2 2 |13 |
|3 3 |15 |