Description
We are playing a game and there will be only one winner in this game eventually. Initially, we have a set of people who form a circle. Then, given a start person, we iteratively remove one person based on certain rule, until only one person left. The last person is called the winner.
The rule is
- Each person holds one ID and one QQ value (an integer).
- All people form a circle. Whenever a player is removed, the remaining people still form a circle.
- When a person, called A, is removed (eg: A’s ID is 3), the next person to be removed is based on A’s QQ value. That is, at the next iteration, we remove the QQ-th person at A’s clockwised direction when the QQ value is positive, and we remove the QQ-th person at A’s anti-clockwised when the QQ value is negative. QQ value does not equal 0 in our test cases.
- Given the start person’s ID, the winner is the last person in the circle.
Example:
3 (the number of people, there IDs are 1, 2, 3 in this case and form a circle clockwised)
4 3 2 (the QQ values of the persons respectively. That is, the person with ID=1 has QQ value=4)
1 (the start person’s ID)
First line: total number of people in this game
Second line: the QQ values of the people
Third line: start person’s ID
Note:
NO STL are allowed.
Time and memory are both limited.
<string> is allowed
Input
0 < Number of people < 1,000,000
QQ Value is an integer but except 0
1 <= The start person's ID <= Number of people
May have several testcases
Output
Output the winner's ID