Simulated Process Scheduling

This problem requires you to simulate an operating system’s process scheduling on a single CPU. Each process is given by its arrival time, execution time, and a natural number representing its priority (a larger number indicates a higher priority). The scheduling works as follows:

• If a process arrives when the CPU is idle, it starts execution immediately and continues until it finishes unless a new process with strictly higher priority arrives.
• If a process arrives while the CPU is busy executing a process with a higher or equal priority, the new process is added to a waiting queue.
• If during the execution of a process, a new process arrives that has a higher priority than the currently running process, the running process is preempted (its remaining time is saved) and moved to the waiting queue. The new higher-priority process begins execution immediately.
• Whenever the CPU becomes idle, if there are waiting processes, the process with the highest priority is selected. In the event of a tie in priority, the process with the earlier arrival time is chosen.

You need to output the finish time for each process in the same order as they appeared in the input.

The formulas used are as follows:

Let \( r_i \) be the remaining execution time for process \( i \). If a process runs from time \( t \) to \( t+\delta \), then its remaining time is updated by

\[ r_i \leftarrow r_i - \delta \]

If the process does not finish, its finish time is not recorded until after it eventually completes its remaining execution.

inputFormat

The first line contains an integer \( N \) representing the number of processes. Each of the next \( N \) lines contains three integers separated by spaces: the arrival time \( A_i \), execution time \( B_i \), and priority \( P_i \) of the \( i^{th} \) process.

\(1 \leq N \leq 10^5\). \(A_i, B_i, P_i\) are non-negative integers with \(P_i \ge 1\).

outputFormat

Output \( N \) lines. The \( i^{th} \) line should contain the finish time of the \( i^{th} \) process as given in the input.

sample

3
0 5 1
1 3 2
2 2 1

8
4
10

</p>