|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|2 초||512 MB||6||4||4||66.667%|
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:
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 ≤ 109, 1 ≤ k ≤ min(2·105, 2n)).
The following k lines describe passengers in order they entered the bus.
The i-th of these lines contains integers xi and yi — the row that the i-th passenger chose and the seat in that row (1 ≤ xi ≤ n, 1 ≤ yi ≤ 2), xi is the row number, yi = 1 means that the passenger took the left seat, yi = 2 — the right seat.
Seats for different passengers are distinct.
The first line must contain s1 — the number of passengers that could be Red Ranger, followed by a space and s1 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.
3 4 1 1 1 2 3 2 2 1
3 1 2 4 1 2 0 1 3 4 1 2 3 4