Astfel, după $k$ etape vom avea în total $4[^k^]$ regiuni egale, în formă de romb. Codificarea regiunilor este făcută astfel:
* în prima etapă, rombul inițial se împarte în patru regiuni, codificate în sens trigonometric cu valorile 1, 2, 3 și 4 (ca în figura 2);
* în fiecare din celelalte etape, se reface codificarea, astfel: dacă rombul anterior avea la etapa precedentă codul [$X$], cele patru romburi obținute după divizarea curentă vor avea acum codurile $4*X–3, 4*X–2, 4*X–1, 4*X$ (figura 3).
* în fiecare din celelalte etape, se reface codificarea, astfel: dacă rombul anterior avea la etapa precedentă codul [$X$], cele patru romburi obținute după divizarea curentă vor avea acum codurile $4X - 3, 4X - 2, 4X - 1, 4X$ (figura 3).
!problema/romb2?romb1.png!
!problema/romb2?romb2.png!
!problema/romb2?romb3.png!
h2. Cerință
Împăratul dorește să știe după cele $k$ etape, care este codul regiunii unde se află un oraș dat prin coordonatele $(Cx, Cy)$.
h2. Date de intrare
Fișierul de intrare $romb2.in$ ...
Pe prima linie a fișierului $romb2.in$ se află numărul $T$ de întrebări (seturi de date de test). Pe fiecare din următoarele $T$ linii se află câte un set de date de test cu valorile $dx, dy, k, Cx, Cy$, cu semnificația anterioară, separate prin câte un spațiu.
h2. Date de ieșire
În fișierul de ieșire $romb2.out$ ...
Fișierul $romb2.out$ va conține $T$ linii, pe fiecare linie $i$ fiind răspunsul la întrebarea [$i$], un număr natural reprezentând codul regiunii în care se află orașul de coordonate date (pentru testul [$i$]).
h2. Restricții
h2. Restricții și precizări
* $... ≤ ... ≤ ...$
* $-20.000 < dx, dy, Cx, Cy < 20.000; 0 < k < 30; 0 < T < 100.000;$
* Pentru $50%$ din teste, $0 < k < 20; 0 < T < 10;$
* $dx$ și $dy$ sunt numere naturale, iar $Cx$ și $Cy$ sunt numere întregi;
* Se garantează că punctul de coordonate $(Cx, Cy)$ nu se află pe granița dintre două regiuni sau pe granița țării. (*Formularea originală de la ONI:* Se garantează că punctul de coordonate $(Cx, Cy)$ nu se află la distanță mai mică de 10^-7^ față de latura unui romb obținut în ultima etapă).
h2. Exemplu
