모눈종이 접기

정사각형 칸으로 이루어진 $N \times N$ 크기의 모눈종이가 있다. $N$은 2의 거듭제곱이다.

칸에는 위쪽 줄부터 차례로, 한 줄 안에서는 왼쪽에서 오른쪽으로 $1$부터 $N^2$까지 번호를 매긴다. 각 칸에는 그 칸의 번호만 적혀 있다.

이 종이를 반으로 접는 동작을 되풀이한다. 먼저 아래쪽 절반을 위쪽 절반 위로 접고, 그다음 오른쪽 절반을 왼쪽 절반 위로 접는다. 접힌 종이가 $1 \times 1$ 크기가 될 때까지 두 동작을 이 순서로 번갈아 수행한다.

다 접고 나면 칸은 $1 \times 1 \times N^2$ 크기의 기둥을 이룬다. 이 기둥을 맨 아래 칸부터 맨 위 칸까지 읽어서 얻은 번호의 수열을 $S = \langle S_1, S_2, \ldots, S_P, \ldots, S_{N^2} \rangle$이라고 하자. $P$는 수열에서의 위치를 뜻한다.

지루한 회의에 앉아 있던 개발자가 종이를 접어 이런 기둥을 만들면서 다음 두 질문의 답을 구하려고 한다.

• 1번 질문. 번호 $X$가 주어진다. 이 번호는 수열 $S$의 몇 번째 위치 $P$에 있는가?
• 2번 질문. 수열 $S$의 위치 $P$가 주어진다. 이 위치에 있는 번호 $X$는 무엇인가?

질문의 종류에 따라 번호 $X$ 또는 위치 $P$를 구하는 프로그램을 작성하시오.

첫째 줄에 질문의 개수 $Q$가 주어진다. 다음 $Q$개의 줄에는 각각 세 정수 $T$, $K$, $V$가 공백 하나로 구분되어 주어진다.

• $T$는 질문의 종류이다. $T = 1$ 또는 $T = 2$이다.
• $K$는 종이의 크기를 정하는 지수이다. 종이의 크기는 $N = 2^K$이다.
• $V$는 $T = 1$이면 번호 $X$이고, $T = 2$이면 위치 $P$이다.

질문마다 한 줄씩, 모두 $Q$개의 줄을 출력한다. 각 줄에는 질문의 종류에 따라 위치 $P$ 또는 번호 $X$를 정수 하나로 출력한다.

• $1 \le Q \le 10000$
• $1 \le T \le 2$
• $0 \le K \le 31$
• $1 \le X, P \le N^2$, 여기서 $N = 2^K$이다.

$N = 2$일 때 기둥을 아래에서 위로 읽으면 $S = \langle 1, 3, 4, 2 \rangle$이다.

$N = 4$일 때는 $S = \langle 1, 13, 16, 4, 8, 12, 9, 5, 6, 10, 11, 7, 3, 15, 14, 2 \rangle$이다.