Round Robin Scheduler

Time limit2sMemory limit512 MB

Summary

Given each job's required seconds, compute its finishing time under a round robin scheduler that grants one second per turn in index order.

Level: Medium6 of 10
Topics: Sorting, Prefix sum, Segment tree
Solved: No attempts yet

Problem

A single CPU runs several jobs at once, and the scheduler tells the CPU which job to run and when.

The scheduler in this problem is a round robin scheduler. There are $N$ jobs, numbered 0 through $N-1$ . Starting from job 0, the scheduler runs the jobs in order of their numbers and gives each job exactly 1 second per turn. After the last job it goes back to job 0 and repeats the same order. A job that has already finished is skipped and never runs again.

The scheduler starts at time 0, and one turn takes exactly 1 second.

Given the time each job needs, write a program that finds when each job finishes.

Input

The first line contains the number of jobs $N$ ( $1 \le N \le 100\,000$ ).

The second line contains the time each job needs, from job 0 through job $N-1$ , separated by spaces. Each of these times is an integer between $1$ and $1\,000\,000\,000$ .

Output

Print $N$ lines. Give the completion time of job 0 first and the completion time of job $N-1$ last.

Examples4

Example 1
Input
```
4
2 1 2 4
```
Expected output
```
5
2
6
9
```
Example 2
Input
```
3
1 2 3
```
Expected output
```
1
4
6
```
Example 3
Input
```
4
3 2 2 1
```
Expected output
```
8
6
7
4
```
Example 4
Input
```
5
8 1 3 3 8
```
Expected output
```
22
2
11
12
23
```