12641264 SUSTech Online Judge
Problem 1264 --Difficult Josephus problem

1264: 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

HINT

Source

2019Fall_DSAA_Lab3 

[Submit][Status]