16245번 - Rangers in the Bus 다국어

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.

The first line of input contains two integers: n and k — the number of rows and the number of passangers (1 ≤ n ≤ 10⁹, 1 ≤ k ≤ min(2·10⁵, 2n)).

The following k lines describe passengers in order they entered the bus.

The i-th of these lines contains integers x_i and y_i — the row that the i-th passenger chose and the seat in that row (1 ≤ x_i ≤ n, 1 ≤ y_i ≤ 2), xi 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.

The first line must contain s₁ — the number of passengers that could be Red Ranger, followed by a space and s₁ 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.