Problem D: Difficult Josephus problem

## Problem D: Difficult Josephus problem

Time Limit: 3 Sec  Memory Limit: 256 MB
Submit: 702  Solved: 201
[Submit][Status][Web Board]

## Description

Josephus problem is a theoretical problem related to a certain counting-out game. However, Narnal thought this problem is too easy for him, so he constructed a more complex Josephus problem as following.

There are $$n$$ people standing in a circle indexing from $$1$$ to $$n$$, and each person in the circle holds a note marked with a positive integer. At first, given a positive integer $$m$$, people count the number from one to the next starting from index $$1$$ in clockwise ($$1, 2, \ldots, n, 1, 2, \ldots$$). When the counted number reaches $$m$$, the corresponding person will be eliminated from the circle and yell the number in his/her note, denoted by $$k_{i}$$, and then people restart counting from the next person targeting for number $$k_{i}$$ until, eventually, only one person is left in the circle.

## Input

First line will be a positive integer $$T$$, which is the number of test cases.

In each test case, the first line would be two integers $$n$$ and $$m$$, where $$n$$ is the initial number of people, and $$m$$ is the initial target counting number.

Then there will be a single line containing $$n$$ integers, indicating the number on each person's note, from index $$1$$ to index $$n$$.

$$T \leq 100, 1 \leq n \leq 10^{4}$$. $$m$$ and each number on the notes will be in the range of $$[1, 10^{8}]$$. We guarantee that there are no more than $$20$$ cases with $$n > 5 \times 10^{3}$$.

## Output

For each case, output one line with one integer for the index of the remaining people.

## Sample Input

2
5 2
2 2 2 2 2
10 10
100000000 1 2 3 4 5 6 7 8 9

## Sample Output

3
1

[Submit][Status]