bafta

"Baftă la ONI 2026! Succes și Noroc au fost la baraj 2025"

Sala de concurs de la ONI 2026 poate fi reprezentată ca o matrice pătratică, în care liniile sunt numerotate de sus în jos de la $0$ la $2^N$, iar coloanele sunt numerotate de la stânga la dreapta de la $0$ la $2^N$. Fiecare element al matricii reprezintă o bancă. Poziția unei bănci va fi identificată prin numărul liniei și numărul coloanei pe care se află.

Pe marginea sălii (linia $0$, linia $2^N$, coloana $0$ și coloana $2^N$) se află profesorii supraveghetori (toate aceste locuri sunt considerate ocupate de la început). Astfel, elevii pot ocupa doar cele $(2^N - 1) \times (2^N - 1)$ bănci din interiorul sălii, situate pe linii și coloane cu numere de la $1$ la $2^N - 1$.

Definim distanța dintre două bănci situate în pozițiile $(L_1, C_1)$ și $(L_2, C_2)$ ca fiind $\max(|L_1 - L_2|, |C_1 - C_2|)$, unde cu $|x|$ s-a notat modulul numărului $x$ ($|x| = x$, dacă $x \ge 0$, respectiv $-x$, dacă $x < 0$).

În acest an, așezarea elevilor în bănci se face într-un mod mai special. Elevii intră în sală pe rând pentru a susține proba și se așază în bănci exact în ordinea în care intră. Când un elev intră în sală, analizează fiecare bancă neocupată, pentru a determina cea mai mică dintre distanțele de la aceasta până la fiecare bancă ocupată (fie de un supraveghetor, fie de alt elev). Apoi se așază într-o bancă neocupată pentru care această distanță este maximă. Dacă există mai multe bănci neocupate care respectă această condiție, elevul trebuie să se așeze în prima, adică cea care este situată pe linia cu numărul cel mai mic, iar în caz de egalitate a liniilor, cea situată pe coloana cu numărul cel mai mic.

Pentru ca profesorii supraveghetori să verifice rapid dacă elevii s-au așezat corect, au nevoie de un program care să răspundă la întrebări de forma $N \ K$, cu semnificația: "În ce bancă se va așeza al $K$-lea elev care intră într-o sală de concurs de dimensiune $(2^N + 1) \times (2^N + 1)$, respectând regulile de mai sus?".

Cerință

Scrieți un program care răspunde la $Q$ întrebări de forma descrisă în enunț.

Date de intrare

Fișierul de intrare bafta.in conține pe prima linie un număr natural $Q$, reprezentând numărul de întrebări. Următoarele $Q$ linii conțin cele $Q$ întrebări, câte o întrebare pe o linie. O linie care descrie o întrebare conține două numere naturale $N$ și $K$, separate prin spațiu, cu semnificația din enunț.

Date de ieșire

Fișierul de ieșire bafta.out conține $Q$ linii. Pe linia $i$ ($1 \le i \le Q$) sunt scrise două numere naturale separate printr-un spațiu, reprezentând poziția băncii (linie, coloană) care este răspunsul la cea de-a $i$-a întrebare citită.

Restricții și precizări

• $2 \le Q \le 10^5$
• $2 \le N \le 30$
• $1 \le K \le \min(10^9, (2^N - 1)^2)$

Exemplu

bafta.in

5
3 1
3 2
3 5
3 9
4 10

bafta.out

4 4
2 2
4 2
6 6
2 2

Explicație

Pentru $N = 3$, sala are $9 \times 9$ bănci, dar supraveghetorii ocupă linia/coloana $0$ și linia/coloana $8$. Rămân în interior $7 \times 7 = 49$ de bănci pentru elevi. Primul elev alege banca din poziția $(4, 4)$; distanța dintre el și cel mai apropiat supraveghetor este maximă ($4$). Al doilea elev alege banca din poziția $(2, 2)$; atât primul elev, cât și cel mai apropiat supraveghetor se află la distanța maximă $2$.