23310번 - 즐거운 과제 라이프

문제

컴퓨터과학과의 교수님들은 학생들을 기쁘게 하기 위해 과제를 비슷한 시기에 내주신다.

이번 학기 6ドル$전공을 채워 넣은 태호는 교수님들의 과제 공격을 받고 정신을 못 차리고 있다.

각각의 과제는 $X_i$ 일 동안 하면 마무리가 되는데, 태호는 이틀 연속으로 똑같은 과목의 과제를 하면 일찍 질려버린다. 결국 태호는 매일 매일 다른 과목의 과제를 하기로 결정했다. 만약 $N$개의 과제를 해야 한다면, 1ドル$일 차엔 첫 번째 과제를 하고, 2ドル$일 차에는 두 번째 과제를 하고, ... $N$일차에는 $N$번째 과제를 한 후, 다시 $N + 1$일차에 첫 번째 과제를 하는 것을 반복하려고 한다.

단, 쉬는 날 없이 과제만 하게 되면 과로사를 할 수 있음으로, $M - 1$일 동안 과제를 하고 $M$일차에 휴식을 취하는 것을 반복할 것이다. 그러나 쉬는 날에 원래 해야 할 과제가 있다면, 그 과제를 다음날로 미루지 않고 아예 하지 않고 넘어갈 것이다.

예를 들어, 5ドル$개의 과제가 있고 4ドル$일에 한 번씩 쉰다고 가정하면, 1ドル$일 차에는 1ドル$번 과제를, 2ドル$일 차에는 2ドル$번 과제를, 3ドル$일 차에는 3ドル$번 과제를 수행한다. 4ドル$일 차에는 4ドル$번 과제를 수행해야 하나, 휴식일이기 때문에 수행하지 않고 넘어간다. 대신, 5ドル$일 차에는 4ドル$번 과제가 아닌 5ドル$번 과제를 수행해야 한다.

만족스러운 플랜을 짰다고 생각해 스스로 만족한 태호였으나, 막상 만들고 보니 과제를 언제 끝낼 수 있을지 궁금해졌다.

과제를 완료하는데 필요한 날의 정보와 휴식일의 정보가 주어질 때, 가장 먼저 끝나는 과제를 구해보자.

입력

첫 줄에는 $N$과 $M$이 주어진다. (2ドル \le N \le 20\ 000,ドル 2ドル \le M \le 500$)

두 번째 줄에 $X_1,ドル $X_2,ドル ..., $X_N$가 공백으로 구분되어 주어진다. (1ドル \le X_i \le 125\ 000\ 000$)

출력

태호가 가장 먼저 끝내는 과제의 번호를 출력한다.

제한

힌트