Train Schedules

You are given the number of trains and their corresponding arrival times and travel durations. When a train arrives, it will start its journey at the maximum of its arrival time and the finish time of the previous train. The finish time for each train is computed using the formula:

\( finish_i = \max(finish_{i-1}, arrival_i) + travel_i \)

Your task is to simulate the scheduling of the trains and output the finish time for each train.

inputFormat

The first line of input contains a single integer \(n\) (1 \(\le\) \(n\) \(\le\) 10^5) representing the number of trains. Each of the next \(n\) lines contains two space-separated integers: \(arrival_i\) and \(travel_i\), representing the arrival time and the travel duration of the \(i^{th}\) train respectively.

outputFormat

Output a single line containing \(n\) space-separated integers, where the \(i^{th}\) integer is the finish time of the \(i^{th}\) train.

3
1 5
2 2
2 3

6 8 11