Wyliczanka

Interview

Time limit6sMemory limit1024 MB

Summary

Given N children in a circle and step counts X1 to XN, the task is to output the order in which children leave, each round removing the child reached by the Xi-th tap.

Level: Medium5 of 10
Topics: Array, Simulation, Segment tree
Solved: No attempts yet

Statement

Children from Bajtogród invented a new game called Wyliczanka.

N children numbered 1, 2, ..., N take part, and each child receives a different number. The children then stand in a circle so that child i sees the back of child i+1, and child N sees the back of child 1.

The game starts with child 1 saying an integer X1. Child 1 taps the back of the child standing in front of them. The tapped child taps the back of the next child, and so on, until the X1-th tap happens. The child tapped last leaves the circle. The child who would have been tapped next says the next number X2. The game ends when only one child remains in the circle.

For a given N and the successive values Xi, determine which child drops out in each round.

Input

The first line contains a natural number N ( $1 \le N \le 1\,000\,000$ ). The second line contains N natural numbers $X_i$ ( $1 \le X_i \le 10^9$ ).

Output

Print N natural numbers, the numbers of the children in the order they leave the circle.

Examples3

Example 1
Input
```
5
3 2 4 1 1
```
Expected output
```
4 2 5 3 1
```
Example 2
Input
```
9
1 2 3 4 5 6 7 8 9
```
Expected output
```
2 5 9 7 8 4 1 3 6
```
Example 3
Input
```
6
6 12 18 24 30 36
```
Expected output
```
1 4 2 3 5 6
```