D - Marking Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

0 から N-1 までの番号がつけられた N 個のマスが並んでいます。 今から、すぬけくんが以下の手順に従って全てのマスに印をつけていきます。

  1. マス 0 に印をつける。
  2. 次の i - iii の手順を N−1 回繰り返す。
    1. 最後に印をつけたマスの番号を A としたとき、変数 x を (A+D) \bmod N で初期化する。
    2. マス x に印が付いている限り、 x を (x+1) \bmod N に更新することを繰り返す。
    3. マス x に印をつける。

すぬけくんが 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\ (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

N=4,D=2 のとき、すぬけくんは以下のように印をつけていきます。

  1. マス 0 に印をつける。
  2. (1回目) x=(0+2)\bmod 4=2 と初期化する。マス 2 は印がついていないので、印をつける。
    (2回目) x=(2+2)\bmod 4=0 と初期化する。マス 0 は印がついているので、x=(0+1)\bmod 4=1 と更新する。マス 1 は印がついていないので、印をつける。
    (3回目) x=(1+2)\bmod 4=3 と初期化する。マス 3 は印がついていないので、印をつける。

Score : 400 points

Problem Statement

There are N squares indexed 0 through (N-1) arranged in a line. Snuke is going to mark every square by the following procedure.

  1. Mark square 0.
  2. Repeat the following steps i - iii (N-1) times.
    1. Initialize a variable x with (A+D) \bmod N, where A is the index of the square marked last time.
    2. While square x is marked, repeat replacing x with (x+1) \bmod N.
    3. Mark square x.

Find the index of the square that Snuke marks for the K-th time.

Given T test cases, find the answer for each of them.

Constraints

  • 1\leq T \leq 10^5
  • 1\leq K\leq N \leq 10^9
  • 1\leq D \leq 10^9
  • All values in the input are integers.

Input

The input is given from Standard Input in the following format, where \mathrm{test}_i denotes the i-th test case:

T
\mathrm{test}_1
\mathrm{test}_2
\vdots
\mathrm{test}_T

Each test case is given in the following format:

N D K

Output

Print T lines.

The i-th (1\leq i \leq T) line should contain the answer to the i-th test case.

Sample Input 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

Sample Output 1

0
2
1
3
0
3
1
4
2

If N=4 and D=2, Snuke marks the squares as follows.

  1. Mark square 0.
  2. (1-st iteration) Let x=(0+2)\bmod 4=2. Since square 2 is not marked, mark it.
    (2-nd iteration) Let x=(2+2)\bmod 4=0. Since square 0 is marked, let x=(0+1)\bmod 4=1. Since square 1 is not marked, mark it.
    (3-rd iteration) Let x=(1+2)\bmod 4=3. Since square 3 is not marked, mark it.