有一排奶牛，最初（即在时间 $t = 0$ 时）只包含位于位置 $0$ 的奶牛 $0$（这里，如果一只奶牛前面有 $k$ 只奶牛，则它处于位置 $k$）。在时间 $t = 1, 2, 3, \dots$ 时，位于位置 $0$ 的奶牛移动到位置 $\lfloor t/2\rfloor$，位于位置 $1\dots \lfloor t/2\rfloor$ 的每只奶牛都向前移动一个位置（即位置编号减 1），且奶牛 $t$ 加入到队伍的末尾（位置 $t$）。

回答 $Q$（$1\le Q\le 10^5$）个独立的询问，每个询问为以下类型之一：

1. 在时间 $t$ 刚结束时，奶牛 $c$ 处于什么位置（$0\le c\le t\le 10^{18}$）？
2. 在时间 $t$ 刚结束时，处于位置 $x$ 的是哪只奶牛（$0\le x\le t\le 10^{18}$）？

输入格式

第一行包含询问的数量 $Q$。

接下来的 $Q$ 行，每行包含三个整数，表示一个形如 1 c t 或 2 x t 的询问。

输出格式

对每个询问，在一行中输出其答案。

样例

输入样例 1

2
1 4 9
2 2 9

输出样例 1

2
4

说明 1

在不同时间刚结束时的队伍情况如下：

t = 0 | 0
t = 1 | 0 1
t = 2 | 1 0 2
t = 3 | 0 1 2 3
t = 4 | 1 2 0 3 4
t = 5 | 2 0 1 3 4 5
t = 6 | 0 1 3 2 4 5 6
t = 7 | 1 3 2 0 4 5 6 7
t = 8 | 3 2 0 4 1 5 6 7 8
t = 9 | 2 0 4 1 3 5 6 7 8 9

在 $t=9$ 刚结束时，奶牛 $4$ 的位置是 $2$，而位于位置 $2$ 的奶牛是 $4$。

输入样例 2

22
1 0 9
1 1 9
1 2 9
1 3 9
1 4 9
1 5 9
1 6 9
1 7 9
1 8 9
1 9 9
2 0 9
2 1 9
2 2 9
2 3 9
2 4 9
2 5 9
2 6 9
2 7 9
2 8 9
2 9 9
1 0 1000000000000000000
2 0 1000000000000000000

输出样例 2

1
3
0
4
2
5
6
7
8
9
2
0
4
1
3
5
6
7
8
9
483992463350322770
148148148148148148

数据范围

• 测试点 3：$Q\le 1000, t\le 100$
• 测试点 4：$t\le 5000$
• 测试点 5-8：所有询问均为类型 1。
• 测试点 9-12：所有询问均为类型 2。