Electric Vehicle Charging Sessions Management

You are given a charging station with N charging slots and M vehicles. Each vehicle arrives at a given time and requires a specific charging duration. When a vehicle arrives:

• If there is an available slot (i.e. less than N vehicles are currently charging), its charging starts immediately at its arrival time.
• If all slots are busy, the vehicle will wait until the earliest slot becomes free. In this case, its start time is the smallest end time among ongoing sessions.

The charging session for a vehicle is represented by a dictionary (or record) containing its vehicle_id, start_time, and end_time. Note that the end time is computed as \(start\_time + charging\_time\) in \(\LaTeX\) format: \(\text{end\_time} = \text{start\_time} + \text{charging\_time}\).

Your task is to schedule the charging sessions for all vehicles based on their arrival times and durations.

inputFormat

The input is read from standard input (stdin) and has the following format:

N M
arrival_time[1] charging_time[1]
arrival_time[2] charging_time[2]
... 
arrival_time[M] charging_time[M]

Where:

• N is the number of charging slots.
• M is the number of vehicles (events).
• Each of the next M lines contains two integers: the arrival time and charging time for each vehicle.

outputFormat

For each vehicle, output a single line in the order of processing (which is the order of input events) with three space-separated integers representing:

1. vehicle_id (starting from 1).
2. start_time of charging.
3. end_time of charging.

The output is printed to standard output (stdout). For vehicles that do not require any charging (if M is 0), no output should be produced.

## sample

3 5
1 5
2 3
6 2
7 4
8 1

1 1 6
2 2 5
3 6 8
4 7 11
5 8 9

</p>