선물 상자

$N$ 명의 어린이가 원형으로 둘러앉아 있다. 어린이들은 시계 방향으로 $1$ 번부터 $N$ 번까지 번호가 붙어있다. $i$ 번 어린이는 $D_i$ 개의 사탕을 담을 수 있는 봉투를 가지고 있다.

몬스터는 최초에 $1$ 번 어린이에서 시작하여 시계 방향으로 어린이를 세어 $M$ 번째까지 간다. 원을 한 바퀴 이상 돌 수도 있다. 몬스터는 $M$ 번째 어린이에게 사탕 $1$ 개를 준다. $M$ 번째 어린이의 봉투가 차면 (즉, 지금까지 받은 사탕이 $D_i$ 개가 되는 경우) 그 어린이는 원에서 빠진다. 사탕을 받은 어린이의 시계 방향 바로 옆 어린이에서 시작하여 $M$ 번째 어린이까지 세고 사탕을 주는 것을 반복한다. 이 과정은 원에 어린이 한 명이 남을 때까지 계속된다. 마지막 어린이에게는 선물 상자를 준다.

이렇게 했을 때, 선물 상자를 받는 어린이의 번호를 출력하여라.

입력 형식

첫 줄에 사람 수 $N$과 문제의 $M$이 공백으로 구분되어 주어진다. ($2 \le N \le 2\,000;$ $1 \le M \le 1\,000\,000\,000$)

둘째 줄에 $N$ 개의 정수가 공백으로 구분되어 주어진다. $i$ 번째 수는 $D_i$를 나타낸다. ($1 \le D_i \le 1\,000\,000\,000$)

출력 형식

첫 줄에 선물 상자를 받는 어린이의 번호를 출력한다.

예제 1

10 1
3 1 4 1 5 9 2 6 5 3

6

예제 2

10 42
3 1 4 1 5 9 2 6 5 3

8

예제 설명

예제 1에서 $1$ 번 어린이가 처음으로 사탕을 받는다. 그 다음 $2$ 번 어린이가 사탕을 받는다. $2$ 번 어린이는 원에서 빠진다. 그리고, 비슷한 과정이 반복된다.

예제 2에서 $M=42$이므로 몬스터가 $42$ 번을 세고 나면 $2$ 번 어린이가 처음으로 사탕을 받는다. 따라서, $2$ 번 어린이가 원에서 처음으로 빠진다. 과정을 반복하다 보면 원에서 마지막으로 남아 선물 상자를 받는 어린이는 $8$ 번이다.

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞추어야 그 종류에 배정된 점수를 받을 수 있다.

해설