← 返回题目列表

AtCoder · agc061_a

A. 长随机播放

中文机器翻译题面 查看原题

分数: 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}(2, 5):
      • 运行 \mathrm{shuffle}(2, 4):
        • \vdots
      • 运行 \mathrm{shuffle}(3, 5):
        • \vdots