Airport Runway Scheduling

You are given a schedule of incoming airplanes. Each airplane is specified by a unique plane_id, an arrival time, and a landing duration. There are two available runways at the airport. Your task is to assign each airplane to one of the two runways such that no two airplanes are using the same runway at the same time.

The scheduling algorithm works as follows: For each airplane in the order given, check if its arrival time is not earlier than the current runway end time for runway 1. If so, assign it to runway 1 and update the runway's end time as \(arrival\_time + duration\). Otherwise, check runway 2 in a similar way. If neither runway is available at the airplane's arrival time, then scheduling fails and the output must be an empty list ([]).

It is guaranteed that the airplanes are provided in the order in which they should be processed. Use the following algorithm to decide the runway assignments:

Initialize runway1_end_time = 0
Initialize runway2_end_time = 0
for each plane (id, arrival_time, duration):
    if arrival_time \(\ge\) runway1_end_time:
         assign plane to runway 1
         update runway1_end_time = arrival_time + duration
    else if arrival_time \(\ge\) runway2_end_time:
         assign plane to runway 2
         update runway2_end_time = arrival_time + duration
    else:
         scheduling fails (output [] immediately)

inputFormat

The input is read from stdin and is structured as follows:

1. An integer n representing the number of airplanes.
2. Followed by n lines, each containing three space-separated integers: plane_id arrival_time duration.

If n is 0, there will be no airplane data.

outputFormat

If a valid scheduling is possible, output the assigned runway for each airplane on a new line in the order they were given. Each line should contain two space-separated integers: plane_id runway, where runway is either 1 or 2.

If it is impossible to schedule the landings according to the rules, output [] (without quotes) on a single line.

## sample

4
1 1 4
2 2 3
3 6 2
4 5 3

1 1
2 2
3 1
4 2

</p>