Pe o masă orizontală se află o bandă super-flexibilă, formată din 2n 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 2n. 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 2n-1 cm. Banda obţinută se poate plia iar în două. Acest procedeu se repetă de n ori, până se obţine grosimea 2n 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 2n).
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.
Să observăm că pătrăţelul special este 2 şi va ajunge în final pe poziţia 6.
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
2 ≤ n ≤ 30
1 ≤ k, s, f ≤ 2n
Pentru 30% dintre teste n ≤ 7.
Pentru 50% dintre teste c=1.
Exemple
banda.in
banda.out
Explicaţii
3
5
1
2
6
În exemple, banda de lungime 23=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).
În al doilea exemplu, se ştie poziţia finală 4, se cere numărul pătrăţelului special (8).
