라운드 로빈 스케줄러

시간 제한2초메모리 제한512 MB

요약

각 작업의 필요 시간을 입력받아 인덱스 순서대로 1초씩 돌아가며 실행하고 끝난 작업을 건너뛰는 라운드 로빈 스케줄러에서 작업별 종료 시각을 구합니다.

난이도: 보통10점 중 6점
유형: 정렬, 누적 합, 세그먼트 트리
정답자: 아직 제출이 없습니다

문제

싱글 CPU에서 여러 작업을 실행할 때, 스케줄러는 어떤 작업을 언제 실행할지 CPU에 알려준다.

이 문제에서 다루는 스케줄러는 라운드 로빈 스케줄러다. 작업은 모두 $N$ 개이고 0번부터 $N-1$ 번까지 번호가 붙어 있다. 스케줄러는 0번 작업부터 번호 순서대로 각 작업을 한 번에 1초씩 실행한다. 마지막 작업까지 실행한 다음에는 다시 0번 작업으로 돌아가 같은 순서를 반복한다. 이미 끝난 작업은 건너뛰고 다시 실행하지 않는다.

스케줄러는 0초에 실행을 시작하고, 한 번의 실행은 정확히 1초가 걸린다.

각 작업을 수행하는 데 필요한 시간이 주어질 때, 각 작업이 언제 끝나는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 작업의 개수 $N$ ( $1 \le N \le 100\,000$ )이 주어진다.

둘째 줄에 각 작업을 수행하는 데 필요한 시간이 0번 작업부터 $N-1$ 번 작업까지 순서대로 공백으로 구분되어 주어진다. 각 시간은 $1$ 이상 $1\,000\,000\,000$ 이하의 자연수다.

출력

$N$ 개의 줄에 걸쳐 각 작업이 완료되는 시각을 0번 작업부터 차례대로 출력한다.

예제4

예제 1
입력
```
4
2 1 2 4
```
예상 출력
```
5
2
6
9
```
예제 2
입력
```
3
1 2 3
```
예상 출력
```
1
4
6
```
예제 3
입력
```
4
3 2 2 1
```
예상 출력
```
8
6
7
4
```
예제 4
입력
```
5
8 1 3 3 8
```
예상 출력
```
22
2
11
12
23
```