分数: 400 点
问题陈述
有 N 已索引的方块 0 通过 (N-1) 排成一排。 Snuke 将按照以下步骤标记每个方块。
- 马克广场 0.
-
重复以下步骤 i - iii (N-1) 次。
- 初始化变量 x 与 (A+D) \bmod N,其中 A 是上次标记的方块的索引。
- 虽然正方形 x 被标记,重复更换 x 与 (x+1) \bmod N.
- 马克广场 x.
找到 Snuke 标记的方块的索引 K第次。
鉴于 T 测试用例,找到每个用例的答案。
约束
- 1\leq T \leq 10^5
- 1\leq K\leq N \leq 10^9
- 1\leq D \leq 10^9
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出,其中 \mathrm{test}_i 表示 i-第一个测试用例:
T
\mathrm{test}_1
\mathrm{test}_2
\vdots
\mathrm{test}_T
每个测试用例均按以下格式给出:
N D K
输出
打印 T 行。
的 i-th (1\leq i \leq T) 行应包含以下问题的答案 i- 第一个测试用例。
示例输入 1
9 4 2 1 4 2 2 4 2 3 4 2 4 5 8 1 5 8 2 5 8 3 5 8 4 5 8 5
示例输出 1
0 2 1 3 0 3 1 4 2
If N=4 和 D=2,Snuke 如下标记方块。
- 马克广场 0.
- (1-st 迭代)让 x=(0+2)\bmod 4=2。 既然方 2 未标记,请标记。
(2-nd迭代)让 x=(2+2)\bmod 4=0。 既然方 0 被标记,令 x=(0+1)\bmod 4=1。 既然方 1 未标记,请标记。
(3-rd迭代)让 x=(1+2)\bmod 4=3。 既然方 3 未标记,请标记。