题目描述

有一条奶牛队列。初始时（即 \(t=0\)）队列中只有编号为 \(0\) 的奶牛，且它位于位置 \(0\)。这里规定：如果一头奶牛前面正好有 \(k\) 头奶牛，那么它的位置就是 \(k\)。

对于每个时刻 \(t=1,2,3,\dots\)，队列会按如下规则变化：

• 原来位于位置 \(0\) 的奶牛移动到位置 \(\left\lfloor \frac{t}{2} \right\rfloor\)
• 原来位于位置 \(1 \dots \left\lfloor \frac{t}{2} \right\rfloor\) 的奶牛都向前移动一格
• 编号为 \(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

输出

2
4

说明

若列出若干时刻结束后的队列，可得：

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

输出

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 类

命题信息

原题命题：Agastya Goel