Description

In this quiz, you are asked to implement a game about passing a bomb. The rules are as follows：

1. N people are playing this game.
   • That is, players are called a₁, a₂ , … a_k.
2. When the game starts, a₁ holds the bomb.
3. In each round afterwards, we have an input number j ≥ 0.

The bomb is passed from its current holder to the next j-th person, and the bomb will explode after the passing completes.

1. After passing, people who passed the bomb in this round need to be reorder.

For example, player a₁ (the current bomb holder) passes the bomb to player a_k, and the bomb will explode at player a_k.

Next, players a₁ to a_k-1 need to change their positions as following:

• a₁ -> a_k-1 -> a₂ -> a_k-2 -> a₃ -> a_k-3 …

Figure: bomb passing sequence

1. If the bomb explodes at player a_k’s hand, a_k dies and is removed from the passing sequence. At the same time, the next player of ak ( a_k+1 ) gets another bomb immediately.
   • For example, if the bomb explodes at the kth player ( a_k )’s hand, then a_k dies and a_k is removed from the sequence. At the same time, a_k+1 obtains another bomb. The new passing sequence starting at the next round would be a₁ -> a_k-1 -> a₂ -> a_k-2 -> a₃ -> a_k-3 …, a_middle , a_k+1, …, a_N, where middle should be ceil((start+end)/2). In this case, middle would be ceil(k/2).
   • If starting player is removed this run, then the passing sequence should start from the next one of starting player.
2. If input j = -1 or only one person remains in the sequence, the game stops.
3. Please print the indices of the remaining players in the sequence, starting at the person who has the bomb. Note when the game stops, there may be one or more players.

 

For example:

At the beginning, we have players numbered 1 to 7, with player 1 initially holding the bomb.

Run 1: j = 9

The passing sequence is as follows: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 1 -> 2 -> 3. Player 3 holds the bomb at the end, so player 3 is removed from the sequence, and the bomb is passed to the next player, which is player 4.

After passing the bomb, we need to reorder their positions. Since every player has now passed the bomb, we reorder the entire sequence from 1 -> 2 -> 4 -> 5 -> 6 -> 7 to 1 -> 7 -> 2 -> 6 -> 4 -> 5, and player 4 holds the bomb.

Run 2: j = 4

The passing sequence is 4 -> 5 -> 1 -> 7 -> 2. Player 2 holds the bomb at the end, so player 2 is removed from the sequence, and the bomb is passed to the next player, which is player 6.

In this run, players 4, 5, 1, 7 have passed the bomb, so we only reorder their positions from 4 -> 5 -> 1 -> 7 to 4 -> 7 -> 5 -> 1, and we need to insert this reordered sequence into the original sequence. The final sequence will be 1 -> 6 -> 4 -> 7 -> 5, and player 6 holds the bomb.

Run 3: j = 2

Following the operations above, the final reordered sequence will be 1 -> 6 -> 4 -> 5.

Run 4: j = -1

When j is -1, there is only one player remaining. In this case, you should output the sequence starting from the player who holds the bomb at the end. Thus, the sequence is 5 -> 1 -> 6 -> 4, as player 5 holds the bomb in the end.

 

Note that all STL library are forbidden.

Input

The first line has one number, N.

The second line has N numbers, denoting the indices of the players.

For the remaining lines, players pass the bomb based on the rules mentioned above.

 

2 ≤ N ≤ 10,000

1 ≤ Player index ≤ 1,000,000

1 ≤ number of remaining lines ≤ 1,000,000

1 ≤ j ≤ 2⁶⁴-1

Output

Please print the indices of the remaining players in the sequence, starting at the person who has the bomb.

Print ' ' (space) between two numbers and '\n' after the last number.

Sample Input  Download

Sample Output  Download

Tags

Discuss