 Final
 Elimination
 Third qual
 Second qual
 First qual
 Warmup
Warmup round completed
Tasks
Show one task per page / all tasks on one page
Time limit  2 seconds 

Memory limit  256 megabytes 
Space Rangers are going to a secret meeting by a bus.
The Main Villain is watching the bus that he thinks the rangers are using. The bus has n rows of seats, each row has two seats: one to the left of the passage, one to the right. Rows are numbered from 1 to n, starting from the front of the bus. There were k passengers that entered the bus at the first stop, the villain knows the order they entered, and who took which seat. Initially all seats were free.
He knows the way rangers choose the seat when they enter the bus:
 Red Ranger likes front seats. When he enters the bus he always chooses the free seat in the minimal row. If both seats are free, he chooses the left one.
 Blue Ranger also likes front seats. But unlike the Red Ranger, he chooses the right seat if both seats in the minimal possible row are free.
 Black Ranger likes back seats. He always chooses the free seat in the maximal row. If both seats in that row are free, he chooses the left one.
 Yellow Ranger also likes back seats, but chooses the right one if possible.
 Pink Ranger has no preferences and just chooses any seat.
For each ranger the villain wants to know who of the k passengers could be that ranger. Note that some rangers could take another bus.
Input format 
The first line of input contains two integers: n and k — the number of rows and the number of passangers (1 ≤ n ≤ 10^{9}, 1 ≤ k ≤ min(2·10^{5}, 2n)). The following k lines describe passengers in order they entered the bus. The ith of these lines contains integers x_{i} and y_{i} — the row that the ith passenger chose and the seat in that row (1 ≤ x_{i} ≤ n, 1 ≤ y_{i} ≤ 2), x_{i} is the row number, y_{i} = 1 means that the passenger took the left seat, y_{i} = 2 — the right seat. Seats for different passengers are distinct. 

Output format 
The first line must contain s_{1} — the number of passengers that could be Red Ranger, followed by a space and s_{1} space separated integers, the numbers of there passengers in order they entered the bus (the passengers are numbered from 1 to k in order they entered the bus). The following four lines must contain the same information about Blue Ranger, Black Ranger, Yellow Ranger, and Pink Ranger, correspondingly. 
Examples 
Input data
3 4 1 1 1 2 3 2 2 1
Output data
3 1 2 4 1 2 0 1 3 4 1 2 3 4 
