I - Circle Pass Game Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

N 人の子供たちが円形に並んでゲームをしています。子供たちには時計回りに 1 から N までの番号が付いており、番号 N の時計回りの隣は番号 1 です。

最初、すべての子供が円陣に参加しており、番号 S の子供がボールを持っています。

これから M 回のパスが行われます。i 回目のパスでは、現在ボールを持っている子供を x として、次の操作を行います。

  1. x の時計回りの隣の位置から時計回りに、円陣に残っている子供（x 自身を除く）だけを順に 1, 2, 3, \ldots と数えていきます。すでに円陣を抜けた子供は飛ばします。残っている子供の人数を超える場合は、円を何周でもして数え続けます。
  2. D_i 番目に数えられた子供にボールを渡します。
  3. その直後、x は円陣から抜けます。以降のパスにおいて x は数えられることも、ボールを受け取ることもありません。

M 回すべてのパスが終わった後、ボールを持っている子供の番号を出力してください。

制約

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq N - 1
  • 1 \leq S \leq N
  • 1 \leq D_i \leq 10^9
  • 入力はすべて整数である

入力

N M S
D_1
D_2
\vdots
D_M
  • 1 行目には、子供の人数 N、パスの回数 M、最初にボールを持っている子供の番号 S がスペース区切りで与えられる。
  • 続く M 行のうち i 行目には、i 回目のパスで数える人数 D_i が与えられる。

出力

M 回すべてのパスが終わった後、ボールを持っている子供の番号を 1 行で出力してください。

入力例 1

5 3 1
1
2
1

出力例 1

5

入力例 2

6 4 3
5
1
7
2

出力例 2

1

入力例 3

20 10 8
3
15
1
22
7
100
4
9
18
2

出力例 3

19

入力例 4

60 30 60
1
59
123456789
17
42
1000000000
8
31
73
2
500
19
64
27
91
6
38
111
25
3
999999937
14
52
7
86
41
12
68
29
5

出力例 4

17

入力例 5

2 1 2
1000000000

出力例 5

1

Score : 400 pts

Problem Statement

N children are standing in a circle playing a game. The children are numbered 1 to N in clockwise order, and the clockwise neighbor of child N is child 1.

Initially, all children are participating in the circle, and child number S is holding the ball.

M passes will be performed. For the i-th pass, let x be the child currently holding the ball, and the following operation is performed:

  1. Starting from the position clockwise next to x, count only the children still remaining in the circle (excluding x itself) in clockwise order as 1, 2, 3, \ldots. Children who have already left the circle are skipped. If the count exceeds the number of remaining children, continue counting by going around the circle as many times as needed.
  2. Pass the ball to the child counted as the D_i-th.
  3. Immediately after, x leaves the circle. In subsequent passes, x will neither be counted nor receive the ball.

After all M passes have been completed, output the number of the child holding the ball.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq N - 1
  • 1 \leq S \leq N
  • 1 \leq D_i \leq 10^9
  • All inputs are integers

Input

N M S
D_1
D_2
\vdots
D_M
  • The first line contains the number of children N, the number of passes M, and the number of the child initially holding the ball S, separated by spaces.
  • The i-th of the following M lines contains D_i, the count number for the i-th pass.

Output

Output in one line the number of the child holding the ball after all M passes have been completed.

Sample Input 1

5 3 1
1
2
1

Sample Output 1

5

Sample Input 2

6 4 3
5
1
7
2

Sample Output 2

1

Sample Input 3

20 10 8
3
15
1
22
7
100
4
9
18
2

Sample Output 3

19

Sample Input 4

60 30 60
1
59
123456789
17
42
1000000000
8
31
73
2
500
19
64
27
91
6
38
111
25
3
999999937
14
52
7
86
41
12
68
29
5

Sample Output 4

17

Sample Input 5

2 1 2
1000000000

Sample Output 5

1