分数: 450 点
问题陈述
有一棵树 N 顶点编号 1 to N。 对于每个 i\ (2 \leq i \leq N),有一条边连接顶点 i 和顶点 \lfloor \frac{i}{2} \rfloor。 没有其他边缘。
在这棵树中,找到与顶点距离 X is K。 这里,两个顶点之间的距离 u 和 v 定义为连接顶点的简单路径中的边数 u 和 v.
你有 T 测试用例解决。 单个文件中的
约束
- 1\leq T \leq 10^5
- 1\leq N \leq 10^{18}
- 1\leq X \leq N
- 0\leq K \leq N-1
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出,其中 \mathrm{test}_i 代表 i-第一个测试用例:
T
\mathrm{test}_1
\mathrm{test}_2
\vdots
\mathrm{test}_T
每个测试用例均按以下格式给出:
N X K
输出
打印 T 行。
的 i第行 (1 \leq i \leq T) 应包含以下问题的答案 i- 第一个测试用例作为整数。
示例输入 1
5 10 2 0 10 2 1 10 2 2 10 2 3 10 2 4
示例输出 1
1 3 4 2 0
树 N=10 如下图所示。

在这里,
- 有 1 顶点, 2,距顶点的距离 2 is 0.
- 有 3 顶点, 1,4,5,距顶点的距离 2 is 1.
- 有 4 顶点, 3,8,9,10,距顶点的距离 2 is 2.
- 有 2 顶点, 6,7,距顶点的距离 2 is 3.
- 没有与顶点距离的顶点 2 is 4.
示例输入 2
10 822981260158260522 52 20 760713016476190629 2314654 57 1312150450968417 1132551176249851 7 1000000000000000000 1083770654 79 234122432773361868 170290518806790 23 536187734191890310 61862 14 594688604155374934 53288633578 39 1000000000000000000 120160810 78 89013034180999835 14853481725739 94 463213054346948152 825589 73
示例输出 2
1556480 140703128616960 8 17732923532771328 65536 24576 2147483640 33776997205278720 7881299347898368 27021597764222976