RRSCHED - Round-Robin Scheduling


A computer processor is given N tasks to perform (1 ≤ N ≤ 50,000). The i-th task requires Ti seconds of processing time (1 ≤ Ti ≤ 1,000,000,000). The processor runs the tasks as follows: each task is run in order, from 1 to N, for 1 second, and then the processor repeats this again starting from task 1. Once a task has been completed, it will not be run in later iterations. Determine, for each task, the total running time elapsed once the task has been completed.

Input

The first line of the input contains the integer N, and the next N lines contain the integers T1 through TN.

Output

Output N lines, the i-th of which contains an integer representing the time elapsed when task i has been processed.

Example

Input:
5
8
1
3
3
8

Output:
22
2
11
12
23

The second task is completed during the first iteration, finishing 2 seconds in. On the third iteration, the third and fourth tasks complete at 11 seconds and 12 seconds, respectively. Finally, on the eighth iteration, the first and last tasks complete at 22 seconds and 23 seconds, respectively.

Warning: large input/output data.

Note: This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2006, TopCoder, Inc. All rights reserved.

(See this post for more information.)


hide comments
danicoder_7: 2023-11-08 18:30:22

i am getting TLE on simulation. any clever solutions?

coolio_1: 2020-03-09 18:00:01

Not using long long int cost me 1WA. Classic BIT;

akt_1998: 2017-07-02 16:41:18

BIT

Shikhar: 2016-02-16 16:31:47

use long long int for answer, it cost me 3 WA

Last edit: 2016-02-16 16:32:05
alpha coder: 2015-12-12 23:58:18

in one go ! :D

humble_coder: 2014-11-08 04:47:24

one way i know is
while(scanf("%d",&n)!=EOF){
...do stuff
}
but here no. of tasks is specified so not needed

Last edit: 2014-11-08 04:48:05
Codeblooded: 2013-09-24 12:04:55

There is only 1 test case.
You need not read till EOF.

preetam: 2013-02-01 17:05:31

tried all cases.. so damn frustrating to get WA..
how do we take input??
while(cin>>n)
{
----do stuff
}

above is fine?


Added by:Neal Wu
Date:2008-07-02
Time limit:0.305s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO
Resource:TopCoder High School SRM 52 (with raised constraints)