A Pleasant Homework Life

The professors of the computer science department hand out their assignments around the same time to make the students happy.

Taeho, who has filled his semester with $6$ majors, is being bombarded by the professors' assignments and cannot collect himself.

Each assignment is finished after working on it for $X_i$ days. However, Taeho gets bored early if he works on the same subject's assignment two days in a row. So he decided to work on a different subject's assignment every day. If he has $N$ assignments to do, he works on the first assignment on day $1$, the second on day $2$, ..., the $N$-th on day $N$, then goes back to the first assignment on day $N+1$, and repeats.

But working on assignments without a break could kill him from overwork, so he repeats working for $M-1$ days and resting on day $M$. If an assignment is due on a rest day, he does not push it to the next day; he skips it entirely.

For example, suppose there are $5$ assignments and he rests once every $4$ days. On day $1$ he does assignment $1$, on day $2$ assignment $2$, and on day $3$ assignment $3$. On day $4$ he should do assignment $4$, but since it is a rest day he skips it. Instead, on day $5$ he does assignment $5$, not assignment $4$.

Taeho, satisfied that he made a pleasant plan, became curious about when he would finish the assignments.

Given the days needed to complete each assignment and the rest day information, find the assignment that finishes first.

The first line gives $N$ and $M$. ($2 \le N \le 20\,000$, $2 \le M \le 500$)

The second line gives $X_1$, $X_2$, ..., $X_N$ separated by spaces. ($1 \le X_i \le 125\,000\,000$)

Print the number of the assignment Taeho finishes first.