==Include(page="template/taskheader" task_id="z")==
==Include(page="template/raw")==
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:
h1. Z-parcurgere
|=. 1|=. 2|
|=. 3|=. 4|
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|
Daca $n=2$, Petrica va traversa patratelele in ordinea:
|=.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 |
|2 2 |13 |
|3 3 |15 |
|4 3 | |
table(example). |_. z.in|_. z.out|
|2 2
3 3
4 3
|13
15|
==Include(page="template/taskfooter" task_id="z")==
