D - A Journey of Sugoroku Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋君はすごろくで遊んでいます。

すごろくの盤面には 1 から N までの番号がついた N 個のマスが一直線上に並んでいます。

各マス i には整数 A_i が書かれています。

高橋君は最初、マス 1 にいます。

彼はこれから K 回の移動を行います。

1 回の移動では、以下の規則に従って現在のマスが更新されます。いずれの場合も移動 1 回分として数えます。

  • N=1 のとき、高橋君は常にマス 1 に留まります。
  • N \ge 2 のとき、現在のマスを i として、次のように移動します。
  • i = N のとき、高橋君はマス N に留まります。
  • i = 1 のとき、A_1 と A_2 の和が偶数ならばマス 2 に進みます。奇数ならばマス 1 に留まります。
  • 2 \le i \le N-1 のとき、A_i と A_{i+1} の和が偶数ならばマス i+1 に進みます。奇数ならばマス i-1 に戻ります。

K 回の移動をすべて終えたとき、高橋君がいるマスの番号を求めてください。

制約

  • 1 \le N \le 2 \times 10^5
  • 1 \le K \le 10^{18}
  • -10^9 \le A_i \le 10^9
  • 入力はすべて整数である

入力

N K
A_1 A_2 \cdots A_N
  • 1 行目には、マスの数を表す整数 N と、移動の回数を表す整数 K が、スペース区切りで与えられる。
  • 2 行目には、A_1, A_2, \ldots, A_N がスペース区切りで与えられる。

出力

K 回の移動終了後に高橋君がいるマスの番号を 1 行で出力してください。

入力例 1

4 5
1 3 2 4

出力例 1

2

入力例 2

3 6
1 2 4

出力例 2

1

入力例 3

8 17
2 4 6 8 10 11 13 15

出力例 3

4

入力例 4

15 1000000000000
-10 -8 -6 -4 -2 0 2 4 6 8 10 12 14 16 18

出力例 4

15

入力例 5

1 1000000000000000000
-123456789

出力例 5

1

Score : 400 pts

Problem Statement

Takahashi is playing sugoroku (a board game).

The sugoroku board has N squares numbered from 1 to N arranged in a straight line.

Each square i has an integer A_i written on it.

Takahashi starts on square 1.

He will make K moves from now.

In each move, his current square is updated according to the following rules. Each case counts as one move.

  • When N=1, Takahashi always stays on square 1.
  • When N \ge 2, let i be his current square. He moves as follows:
  • If i = N, Takahashi stays on square N.
  • If i = 1, he advances to square 2 if the sum of A_1 and A_2 is even. He stays on square 1 if it is odd.
  • If 2 \le i \le N-1, he advances to square i+1 if the sum of A_i and A_{i+1} is even. He goes back to square i-1 if it is odd.

Determine the number of the square Takahashi is on after all K moves are completed.

Constraints

  • 1 \le N \le 2 \times 10^5
  • 1 \le K \le 10^{18}
  • -10^9 \le A_i \le 10^9
  • All inputs are integers.

Input

N K
A_1 A_2 \cdots A_N
  • The first line contains an integer N representing the number of squares and an integer K representing the number of moves, separated by a space.
  • The second line contains A_1, A_2, \ldots, A_N separated by spaces.

Output

Print the number of the square Takahashi is on after K moves, on a single line.

Sample Input 1

4 5
1 3 2 4

Sample Output 1

2

Sample Input 2

3 6
1 2 4

Sample Output 2

1

Sample Input 3

8 17
2 4 6 8 10 11 13 15

Sample Output 3

4

Sample Input 4

15 1000000000000
-10 -8 -6 -4 -2 0 2 4 6 8 10 12 14 16 18

Sample Output 4

15

Sample Input 5

1 1000000000000000000
-123456789

Sample Output 5

1