Printer Scheduling

You are given m printers numbered from 1 to m and n print tasks (files). The i-th file arrives at time \(t_i\) and requires \(s_i\) time to be printed.

Each time a file arrives, it is assigned to the printer with the minimum waiting time. The waiting time for a printer is defined as \(\max(0, \text{available_time} - t)\) where \(t\) is the current arrival time. If there are multiple printers with the same waiting time, choose the one with the smallest printer number.

After processing all tasks, output for each printer the list of file indices that were printed by it (files are numbered from 1 to n in the order they arrive). If a printer didn’t print any files, output an empty line.

Note: It is guaranteed that no two files arrive at the same time.

inputFormat

The first line contains two integers m and n representing the number of printers and the number of files, respectively.

Then follow n lines. The i-th of these lines contains two integers \(t_i\) and \(s_i\), the arrival time and the printing duration of the file.

outputFormat

Output m lines. The i-th line should list the file indices printed by printer i in the order they are processed, separated by spaces. If printer i did not print any files, output an empty line.

sample

2 3
1 2
2 4
5 3

1 3
2