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

1. Each person holds one ID and one QQ value (an integer).
2. All people form a circle. Whenever a player is removed, the remaining people still form a circle.
3. 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.
4. 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

Sample Input  Download

Sample Output  Download

Tags

Discuss