说明

本题不再提供额外样例文件。

题目描述

Famer John 要将他的若干头奶牛进行排队，并按进入队伍的顺序给她们编号，不过编号是从 0 开始的。在时刻 0，一头奶牛进入队伍，作为队头，编号为 0；在时刻 1，又有一头奶牛进入队伍，编号为 1；…… 依此类推，在时刻 i 进入队伍的奶牛编号为 i。

在时刻 i，编号为 i 的奶牛即将进入队伍时，排在队头的奶牛（第一个）要移动到第 $\lfloor i/2\rfloor + 1$ 头奶牛（以还未移动的队头作为第一个计数）的身后，其他奶牛不动，然后奶牛 i 进入到队尾。

现在有 T 个询问需要你作出回答，每个询问包含三个整数：p x t，具体含义如下：

• 当 p = 1 时，你需要回答在时刻 t 结束后，编号为 x 的奶牛前面有多少头奶牛？
• 当 p = 2 时，你需要回答在时刻 t 结束后，哪头奶牛前面有 x 头奶牛？你需要输出该奶牛的编号。

输入格式

第一行：一个整数 $T$，表示询问的个数。

接下来 $T$ 行，每行三个整数 p x t，表示一个询问。

输出格式

共 T 行，每行一个整数，依次表示每个询问的答案。

样例输入

5
1 2 5
2 0 5
2 1 5
1 0 102030405060708090
2 12345678987654321 98765432123456789

样例输出

0
2
0
28251512160719421
37037037037037037

样例解释

此处仅解释前三个询问

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

在时刻 5 结束之后

第一个询问：奶牛 2 的前面有 0 头奶牛。

第二个询问：前面有 0 头奶牛的是奶牛 2。

第三个询问：前面有 1 头奶牛的是奶牛 0。

数据范围

100% 的数据：$1 ≤ T ≤ 10^5$, $0 ≤ x ≤ t ≤ 10^{18}$

• 其中 10% 的数据：$T ≤ 1000, t ≤ 100$。
• 另有 20% 的数据：$t ≤ 5000$。
• 另有 30% 的数据：所有的 $p = 1$。
• 另有 40% 的数据：所有的 $p = 2$。