A100977.[USACO26JAN1] Lineup Queries S

一开始只有一头奶牛，编号为 $0$，位于下标 $0$。

接下来进行若干轮操作。对于第 $x$ 轮（$x$ 从 $1$ 开始），令

$$m=\left\lfloor \frac{x}{2}\right\rfloor.$$

这一轮依次执行：

1. 将当前位于下标 $0$ 的奶牛移动到下标 $m$。
2. 原本处于下标区间 $[1,m]$ 的奶牛整体向前移动一格（下标都减 $1$）。
3. 新建一头奶牛，编号为 $x$，并放到下标 $x$。

可以证明：第 $t$ 轮结束后，恰好有 $t+1$ 头奶牛，分别位于下标 $0,1,2,\dots,t$。

你需要回答 $q$ 个询问，每个询问给出一个轮数 $t$ 与一个参数 $x$：

• 询问 1：第 $t$ 轮结束后，编号为 $x$ 的奶牛位于哪个下标？
• 询问 2：第 $t$ 轮结束后，下标为 $x$ 的位置上是哪一头奶牛（输出其编号）？

第一行包含一个整数 $q$，表示询问个数。
接下来 $q$ 行，每行包含三个整数 $op,t,x$：

• 若 $op=1$，表示询问 $1$；
• 若 $op=2$，表示询问 $2$。

对于每个询问输出一行一个整数表示答案。

数据范围

• $1\le q\le 2\times 10^5$；
• $0\le t\le 10^{18}$；
• 对于任意询问，保证 $0\le x\le t$；
• 需要注意读入效率。

样例解释

第 $0$ 轮（初始）

只有编号为 $0$ 的奶牛在下标 $0$：

$$[0]$$

---

第 $1$ 轮

本轮 $x=1$，令

$$m=\left\lfloor \frac{1}{2}\right\rfloor=0.$$

1. 将下标 $0$ 的奶牛（编号 $0$）放到下标 $m=0$（位置不变）。
2. 原本处于区间 $[1,m]=[1,0]$ 的奶牛整体前移一格（该区间为空，无变化）。
3. 新建编号为 $1$ 的奶牛放到下标 $1$。

因此第 $1$ 轮结束后序列（下标 $\to$ 编号）为：

$$[0,\,1]$$

---

第 $2$ 轮

本轮 $x=2$，令

$$m=\left\lfloor \frac{2}{2}\right\rfloor=1.$$

第 $1$ 轮结束时序列为 $[0,1]$，即下标 $0$ 是编号 $0$，下标 $1$ 是编号 $1$。

1. 将下标 $0$ 的奶牛（编号 $0$）移动到下标 $m=1$。
2. 原本处于区间 $[1,m]=[1,1]$ 的奶牛（编号 $1$）整体前移一格，变到下标 $0$。
3. 新建编号为 $2$ 的奶牛放到下标 $2$。

因此第 $2$ 轮结束后序列为：

$$[1,\,0,\,2]$$

由此：

• 询问 $1$（$t=2$）：编号 $1$ 在下标 $0$，输出 $0$
• 询问 $2$（$t=2$）：下标 $0$ 上是编号 $1$，输出 $1$

---

第 $3$ 轮

本轮 $x=3$，令

$$m=\left\lfloor \frac{3}{2}\right\rfloor=1.$$

第 $2$ 轮结束时序列为 $[1,0,2]$。

1. 将下标 $0$ 的奶牛（编号 $1$）移动到下标 $m=1$。
2. 原本处于区间 $[1,1]$ 的奶牛（编号 $0$）整体前移一格，变到下标 $0$。
3. 新建编号为 $3$ 的奶牛放到下标 $3$。
   并且原来下标 $2$ 的奶牛（编号 $2$）不在区间 $[1,1]$ 中，因此保持在下标 $2$。

因此第 $3$ 轮结束后序列为：

$$[0,\,1,\,2,\,3]$$

---

第 $4$ 轮

本轮 $x=4$，令

$$m=\left\lfloor \frac{4}{2}\right\rfloor=2.$$

第 $3$ 轮结束时序列为 $[0,1,2,3]$。

1. 将下标 $0$ 的奶牛（编号 $0$）移动到下标 $m=2$。
2. 原本处于区间 $[1,2]$ 的奶牛（编号 $1$ 和编号 $2$）整体前移一格：
   • 编号 $1$ 从下标 $1$ 变到下标 $0$
   • 编号 $2$ 从下标 $2$ 变到下标 $1$
3. 新建编号为 $4$ 的奶牛放到下标 $4$。
   并且原来下标 $3$ 的奶牛（编号 $3$）不在区间 $[1,2]$ 中，因此保持在下标 $3$。

因此第 $4$ 轮结束后序列为：

$$[1,\,2,\,0,\,3,\,4]$$

由此：

• 询问 $2$（$t=4$）：下标 $2$ 上是编号 $0$，输出 $0$
• 询问 $1$（$t=4$）：编号 $0$ 在下标 $2$，输出 $2$