Задача 38865. Rangers on the bus

It's not every day that the Power Rangers put on their suits. Judge for yourself: how ridiculous they would have looked, say, in public transport, if they had not been removed!
This creates certain difficulties for villains who want to hunt them down. Even today, Rita Repulsa can't catch them because she doesn't know what they look like without their costumes.
Rita is watching a bus that she thinks is one of the Rangers. Inside the bus there are n rows of seats, each of which has two seats — left and right of the aisle. Rows are numbered from 1 to n, starting from the front of the bus. At the final stop, k people got on the bus in turn, and Rita knows who got into which seat and in what order. In addition, she knows how each of the Rangers chooses their seat when they enter the bus:

•  Red Ranger loves to sit in front. Therefore, among the empty seats, he always chooses the place in the row with the smallest number. If there are two free places in this row, he sits to the left of the aisle.
•  The Blue Ranger also likes to sit in front. But, unlike red, when there are two free places in the row with the lowest number, Blue sits on the right.
•  The Black Ranger likes to sit in the back. Among the empty seats, he always chooses the seat in the row with the largest number, and if there are two free seats, he sits to the left of the aisle.
•  Yellow Ranger too, likes to sit in the back. But, unlike black, when two places are free in the row with the highest number, yellow sits on the right.
•  The pink ranger has no preferences and can sit in any free seat.

For each of the rangers, Rita wants to know which of the k passengers could be him. For the known places where passengers boarded, output this information. Please note that not all Rangers have necessarily traveled on this bus.

Input
The first line contains numbers n and k — the number of rows in the bus and the number of  passengers (1 ≤ n ≤ 10⁹, 1 ≤ k ≤ min(2 · 10⁵, 2n)) .
The next k lines describe the passengers in the order they got on the bus.
The i-th of these lines contains numbers x_i and y_i — the seat where the i-th passenger sat (1 ≤ x_i ≤ n, 1 ≤ y_i ≤ 2), x_i — this is the row number, y_i = 1 if it's to the left of the aisle, and y_i = 2 if it's to the right.
All the seats in which the passengers sat are different.

Imprint
In the first line print the number s₁ — the number of passengers who could be a red ranger followed by a space-separated s₁ numbers — the numbers of these passengers are in ascending order (passengers are numbered from 1 to k in the order in which they are given in the input data).
In the next four lines print information about the rest of the rangers in the same format: blue, black, yellow and pink, respectively.
 

Examples

#	Input	Output
1	3 4 1 1 1 2 3 2 2 1	3 1 2 4 1 2 0 1 3 4 1 2 3 4

Remark

This picture shows the seats that the passengers sat in in the example.