Patrat

Se considera un patrat de dimensiune $N \times N$. Bobi vrea sa faca turul chenarului in urmatorul fel:

• Daca se afla pe prima linie si se poate deplasa pe celula din dreapta, se va deplasa pe ea. Altfel, se va deplasa pe urmatoarea linie.
• Daca se afla pe ultima coloana si se poate deplasa pe celula din jos, se va deplasa pe ea. Altfel, se va deplasa pe coloana anterioara.
• Daca se afla pe ultima linie si se poate deplasa pe celula din stanga, se va deplasa pe ea. Altfel, se va deplasa pe linia anterioara.
• Daca se afla pe prima coloana si se poate deplasa pe celula din sus, se va deplasa pe ea. Altfel, se va deplasa pe urmatoarea coloana.

Cerinta

Dandu-se $Q$ perechi de forma $N$ si $K$ (lungimea turului), sa se determine, pentru fiecare, pe care celula se va afla Bobi dupa $K$ pasi, stiind ca el incepe din celula din sus stanga.

Date de intrare

Pe prima linie a fișierului de intrare patrat.in se găseste numarul natural nenul $Q$, cu semnificatia din enunt.
Pe fiecare dintre urmatoarele $Q$ linii ale fișierului de intrare patrat.in se găsesc numerele intregi $N$ si $K$, separate prin spatii, cu semnificatia din enunt.

Date de ieșire

Pe fiecare dintre urmatoarele $Q$ linii ale fișierului de ieșire patrat.out se va găsi o pereche de numere intregi - linia, respectiv coloana pe care se va afla Bobi dupa un tur de $K$ pasi pe un patrat de $N \times N$.

Restricții și precizări

• $1 \leq Q \leq 500\ 000$
• $2 \leq N_i \leq {10}^{12}$
• $0 \leq K_i \leq {10}^{12}$
• Pentru teste in valoare de $15$ puncte: $K_i = 0$
• Pentru alte teste in valoare de $15$ puncte: $K_i \vert N_i$
• Pentru alte teste in valoare de $30$ de puncte: $\sum K_i \leq 1\ 000\ 000$
• Pentru alte teste in valoare de $20$ de puncte: $N_i \leq 2\ 000$
• Pentru alte teste in valoare de $20$ de puncte: nicio restrictie suplimentara.

Exemplu

patrat.in

17
4 0
4 1
4 2
4 3
4 4
4 5
4 6
4 7
4 8
4 9
4 10
4 11
4 12
4 13
4 14
4 15
4 16

patrat.out

1 1
1 2
1 3
1 4
2 4
3 4
4 4
4 3
4 2
4 1
3 1
2 1
1 1
1 2
1 3
1 4
2 4

Explicatie

Dupa $0$ pasi, Bobi se va afla in punctul initial $(1, 1)$. Dupa $1$ pas, se va misca in dreapta s.a.m.d., dupa cum se poate vedea in figura alaturata.