Description

给你一个由 $N\times N$ 个小方块构成的纸片，且N是2的次幂。每个小方格从左到右，从上到下依次编号。每个小方格只放入它自己的编号。这张纸片不断地对半折叠，先是上下折叠，还是左右折叠。直到纸片的大小变成了 $1\times 1$。显然，折叠后的纸片变成了 $N\times N$的一行。我们定义 $S=\langle s_1,s_2,s_3,\dots,s_p,\dots,s_{N\times N}\rangle$，串 $S$ 由这一行的数字构成，其元素依次为折叠后的纸片从最下方的元素到最上方的数字值。正在参加无聊会议的IT专家一时兴起开始叠纸片，然后通过上述方法得到一串字符串。为了打发时间，专家决定找到以下两种问题的答案:

• 问题类型1：给出一个确定的数字 $x$，问 $x$ 和字符串S的第几个元素值相同？
• 问题类型2：给出一个确定的位置 $p$，问字符串中第 $p$ 个位置上的元素值为？

Input Format

第一行包括一个数字 $Q$，问题的数量。

接下来的 $Q$ 行包括 $3$ 个用空格隔开的数字，$T,K,V$

• $T$ - 表示问题的类型( $T = 1$ 或 $2$ )
• $K$ - 表示纸片的规格 $N$ 是 $2^k$
• $V$ - 如果是问题类型 $1$，则是数字 $x$；如果是问题类型 $2$，则是数字 $p$

Output Format

输出应该包含Q行，每行分别为对应问题的答案

Samples

3
1 1 4
2 2 14
1 2 16

3
15
3

样例解释

$K=1$ 时纸片上的数字为

1 2
3 4

则 $S=\langle 1, 3, 4, 2 \rangle$ $K=2$ 时纸片上的数字为

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

则 $S=\langle 1, 13, 16, 4, 8, 12, 9, 5, 6, 10, 11, 7, 3, 15, 14, 2 \rangle $

Hints

• $1 \leq Q \leq 10^5$
• $1\leq T \leq 2$
• $0 \leq K \leq 31$
• $1 \leq x , p \leq N\times N$ ,其中 $N=2^K$