banda

Pe o masă orizontală se află o bandă super-flexibilă, formată din $2^n$ pătrăţele de latură $1$ cm. Grosimea benzii este de $1$ mm. Pătrăţelele sunt numerotate de la stânga la dreapta de la $1$ la $2^n$. Această bandă se poate plia în două, suprapunând o parte peste cealaltă (stânga peste dreapta sau invers). Astfel, anumite poziţii se suprapun şi se obţine grosime dublă şi lungime $2^{n-1}$ cm. Banda obţinută se poate plia iar în două. Acest procedeu se repetă de $n$ ori, până se obţine grosimea $2^n$ mm şi lungimea $1$ cm (adică toată pătrăţelele se vor suprapune, formând o singură coloană).

Folosind o pioneză, vom fixa de masă pătrăţelul $k$ al benzii şi aplicăm procedeul de pliere descris mai sus, obţinând astfel o coloană a cărei bază este pătrăţelul $k$. În cadrul acestei coloane vom numerota poziţiile pătrăţelelor de jos în sus de la $1$ la $2^n$).

Există două tipuri de interogări posibile:

1. Dat fiind un pătrăţel (să-l numim pătrăţel special), să se determine poziţia lui finală (pe coloană).
2. Dată fiind poziţia finală a pătrăţelului special, să se determine numărul său

De exemplu, pentru $n=3$, şi $k=5$ vom obţine.

Figura 1 din enunțul original al problemei banda.Mărește schema ↗

Cerinţă

Date fiind valorile $n$ şi $k$, scrieţi un program care răspunde la o interogare de tipul $1$ sau de tipul $2$.

Date de intrare

Fişierul banda.in conţine $4$ linii. Pe prima linie este scris numărul natural $n$. Pe a doua linie este scris numărul natural $k$, reprezentând poziţia pătrăţelului fixat. Pe cea de a treia linie este scrisă o cifră $c$ care poate fi $1$ sau $2$, indicând tipul interogării. Dacă cifra $c$ este $1$ pe cea de a patra linie este scris numărul natural $s$ reprezentând numărul pătrăţelului special. Dacă cifra $c$ este $2$ pe cea de a patra linie este scris un număr natural $f$ reprezentând poziţia finală a pătrăţelului special.

Date de ieşire

Fişierul banda.out va conţine o singură linie pe care va fi scris un număr natural reprezentând rezultatul interogării

Restricții și precizări

• $2 \leq n \leq 30$
• $1 \leq k, s, f \leq 2^n$
• Pentru $30\%$ dintre teste $n \leq 7$. Pentru $50\%$ dintre teste $c=1$

Exemplul 1

banda.in

3
5
1
2

banda.out

6

Explicație

În exemple, banda de lungime $2^3=8$ cm este fixată de masă pe poziţia $5$.
În primul exemplu, trebuie să aflăm poziţia finală a pătrăţelului $2$ (aceasta este $6$).

Exemplul 2

banda.in

3
5
2
4

banda.out

8

Explicație

În al doilea exemplu, se ştie poziţia finală $4$, se cere numărul pătrăţelului special ($8$).