← 返回题目列表

AtCoder · abc290_d

G. 标记

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

分数: 400 点

问题陈述

有 N 已索引的方块 0 通过 (N-1) 排成一排。 Snuke 将按照以下步骤标记每个方块。

  1. 马克广场 0.
  2. 重复以下步骤 i - iii (N-1) 次。
    1. 初始化变量 x 与 (A+D) \bmod N,其中 A 是上次标记的方块的索引。
    2. 虽然正方形 x 被标记,重复更换 x 与 (x+1) \bmod N.
    3. 马克广场 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 如下标记方块。

  1. 马克广场 0.
  2. (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 未标记,请标记。