Pins and Jumpers
Description
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$.
Given the configuration of jumpers, you should emulate the work of robot InnoKentij.
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.
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.
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.
10 5
2 3
4 5
4 6
3 6
3 10
7 4
5 6
2 2
1 1
1 6
9 6
5 5
4 6
3 7
2 8
3 7
1 9
1 0
1 0
1 1 2
0 0
1 2 1 3
1 0
1 0
1 0
1 3 1 2 3
1 0
1 1 1
1 1 2
1 1 3
0 0
1 1 4