分数: 500 点
问题陈述
有一个数组 A_1, \ldots, A_N,最初 A_i = i 对于所有人 i。定义以下例程 \mathrm{shuffle}(L, R):
- If R = L + 1,交换值 A_L 和 A_R 并终止。
- 否则,运行 \mathrm{shuffle}(L, R - 1) 随后 \mathrm{shuffle}(L + 1, R).
假设我们运行 \mathrm{shuffle}(1, N)。打印值 A_K 例程完成后。
对于每个输入文件,求解 T 测试用例。
约束
- 1 \leq T \leq 1000
- 2 \leq N \leq 10^{18}
- 1 \leq K \leq N
输入
输入由标准输入按以下格式给出:
T case_1 case_2 \vdots case_T
每个案例的格式如下:
N K
输出
打印 T 行。的 i- 第行应包含以下问题的答案 i第一个案例。
示例输入 1
7 2 1 2 2 5 1 5 2 5 3 5 4 5 5
示例输出 1
2 1 2 4 1 5 3
对于 N=2,我们执行以下操作并得到 A=(2,1).
- 运行 \mathrm{shuffle}(1, 2),并交换 A_1 和 A_2.
对于 N=5,我们执行以下操作并得到 A=(2,4,1,5,3).
- 运行 \mathrm{shuffle}(1, 5):
- 运行 \mathrm{shuffle}(1, 4):
- 运行 \mathrm{shuffle}(1, 3):
- \vdots
- 运行 \mathrm{shuffle}(2, 4):
- \vdots
- 运行 \mathrm{shuffle}(1, 3):
- 运行 \mathrm{shuffle}(2, 5):
- 运行 \mathrm{shuffle}(2, 4):
- \vdots
- 运行 \mathrm{shuffle}(3, 5):
- \vdots
- 运行 \mathrm{shuffle}(2, 4):
- 运行 \mathrm{shuffle}(1, 4):