A single CPU runs n tasks using round-robin scheduling with a fixed time quantum q. Task i (0-indexed by input order) becomes available at integer time arrival[i] and needs burst[i] units of CPU time to finish. Time advances in whole units.
The ready queue is a FIFO. The scheduling rules are:
- When the CPU is free it takes the task at the front of the ready queue and runs it for
min(q, remaining)units (its remaining time may be less than a full quantum). - A task is appended to the back of the ready queue at its arrival time. If several tasks arrive at the same instant, they are appended in increasing task-id order.
- When a running task's slice ends at time
tand it still has work left, any task that arrives at exactly timetis appended to the ready queue the just-preempted task is appended back. The preempted task then goes to the back of the queue.
These rules make the whole simulation deterministic. Report the completion time of every task.
Input format
Line 1: two integers n and q separated by a space.
Next n lines: two integers arrival[i] burst[i] for task i, in order i = 0 .. n-1.
Output format
A single line with n integers separated by single spaces: the completion time of each task in input order (task 0 first).
Constraints
- 1 ≤ n ≤ 100000
- 1 ≤ q ≤ 1000000000
- 0 ≤ arrival[i] ≤ 1000000000
- 1 ≤ burst[i] ≤ 1000000000
- The answer is uniquely determined by the rules above.