Noul împărat INFO al ţării ONI2013 a decis să împartă ţara în regiuni codificate după un algoritm stabilit prin decret. Ţara are formă de romb, având centrul în punctul de coordonate (0,0) şi lungimile semi-diagonalelor dx şi dy (ca în figura 1).
Împăratul alege un număr k, reprezentând numărul de etape de parcurs, astfel:
• în prima etapă, rombul iniţial este împărţit în patru regiuni egale, în formă de romb, fiecare latură fiind jumătate din latura rombului iniţial;
• în fiecare dintre celelalte k–1 etape, orice romb rezultat la etapa precedentă este împărţit în alte patru romburi egale, aşa cum este descris în prima etapă.
Astfel, după k etape vom avea în total 4k 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 dintre 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).
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).
Date de intrare
Pe prima linie a fişierului romb1.in se află numărul T de seturi de date de test. Pe fiecare dintre următoarele T linii se află câte un set de date de test cu valorile dx dy k Cx Cy, cu semnificaţia fin enunţ, separate prin câte un spaţiu.
Date de ieşire
Fişierul romb1.out va conţine T linii, pe linia i fiind scris răspunsul la întrebarea i, un număr natural reprezentând codul regiunii în care se află oraşul de coordonate date.
Restricţii
• -20000 < dx, dy, Cx, Cy < 20000
• 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ă la distanţă mai mică de 10-7 faţă de latura unui romb obţinut în ultima etapă.
Exemple
romb1.in
romb1.out
Explicaţii
2
10 8 2 6 -2
12 16 3 -2 4
15
10
Numărul de seturi de date de test este T=2.
Oraşul de coordonate (6,-2), se află în regiunea codificată cu 15
Oraşul de coordonate (-2, 4), se află în regiunea codificată cu 10
