E. Pins and Jumpers
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

The recently-designed electronic board has $$$n$$$ pins numbered from $$$1$$$ to $$$n$$$, arranged in a single row. Several jumpers are going to be put on top of the pins. There are $$$m$$$ jumpers in total, numbered from $$$1$$$ to $$$m$$$. Each jumper is characterised by two numbers — $$$l_j$$$ and $$$r_j$$$: being installed, the $$$j$$$-th jumper covers a contiguous range of pins from $$$l_j$$$ to $$$r_j$$$ (inclusive). Each jumper is constructed in a such way that it will not fit any other position.

Jumper installation process is fully automated. Installation is performed by a very intelligent and innovative robot called InnoKentij as follows.

There is a conveyor, which supplies jumpers to InnoKentij one by one from jumper number $$$1$$$ to jumper number $$$m$$$. For each jumper $$$j$$$, InnoKentij needs to decide whether to install it. If all the pins from $$$l_j$$$ to $$$r_j$$$ (inclusive) are free, InnoKentij simply installs the $$$j$$$-th jumper, and the process continues. But it can happen that the $$$j$$$-th jumper is conflicting with some of previously installed jumpers. Two jumpers are called conflicting if their installation ranges share at least one pin. In case of a conflict, InnoKentij has the following two options:

  • discard the $$$j$$$-th jumper;
  • discard all previously installed jumpers which conflict with the $$$j$$$-th jumper, and install the jumper number $$$j$$$.
InnoKentij is programmed to make a greedy choice during each step: between the provided options, it chooses the one where more pins are covered by jumpers. If both options are equivalent in terms of covered pins, then InnoKentij uses the second option (it discards all jumpers conflicting with the $$$j$$$-th one and installs that jumper). It should be noted that once a jumper is discarded, it can never be installed again, even if the pins it should cover become unoccupied.

Given the configuration of jumpers, you should emulate the work of robot InnoKentij.

Input

The first line of the input contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 4\cdot10^5$$$; $$$1 \le m \le 2\cdot10^5$$$) — the number of pins on the electronic board and the number of jumpers.

The next $$$m$$$ lines describe the jumpers: the $$$j$$$-th of them contains two integers $$$l_j$$$ and $$$r_j$$$ ($$$1 \le l_j \le r_j \le n$$$) — the installation position of the $$$j$$$-th jumper.

Output

You should output the work log of the robot InnoKentij. The log should contain exactly $$$m$$$ lines, the $$$j$$$-th line corresponding to the actions pefrormed by InnoKentij when it was supplied with the $$$j$$$-th jumper from the conveyor. The first integer in $$$j$$$-th line should be $$$1$$$ if the $$$j$$$-th jumper was installed, or $$$0$$$ if it was discarded. The second integer in the $$$j$$$-th line (let's denote it by $$$d_j$$$) should be equal to the number of conflicting jumpers which were discarded (this number can be $$$0$$$ if there were no conflicting jumpers, or if the $$$j$$$-th jumper was discarded). Then, $$$d_j$$$ integers should follow — the indices of the jumpers InnoKentij removed in ascending order.

Examples
Input
10 5
2 3
4 5
4 6
3 6
3 10
Output
1 0
1 0
1 1 2
0 0
1 2 1 3
Input
7 4
5 6
2 2
1 1
1 6
Output
1 0
1 0
1 0
1 3 1 2 3
Input
9 6
5 5
4 6
3 7
2 8
3 7
1 9
Output
1 0
1 1 1
1 1 2
1 1 3
0 0
1 1 4