버스 안의 레인저스

레인저스는 비밀 회의에 가려고 버스를 탄다.

주 악당은 레인저스가 타는 버스를 지켜본다. 버스에는 좌석이 n개 행으로 있고, 각 행에는 통로를 사이에 두고 왼쪽과 오른쪽에 좌석이 하나씩 있다. 행은 버스 앞에서부터 1번부터 n번까지 번호가 붙는다. 첫 정류장에서 버스에 탄 승객은 k명이고, 악당은 이들이 탄 순서와 누가 어느 좌석을 골랐는지 알고 있다. 처음에는 모든 좌석이 비어 있었다.

그는 레인저스가 버스에 탈 때 좌석을 고르는 방식을 알고 있다.

• 레드 레인저는 앞좌석을 좋아한다. 버스에 타면 항상 번호가 가장 작은 행에서 빈 좌석을 고른다. 두 좌석이 모두 비어 있으면 왼쪽을 고른다.
• 블루 레인저도 앞좌석을 좋아한다. 하지만 레드 레인저와 달리, 번호가 가장 작은 행에서 두 좌석이 모두 비어 있으면 오른쪽을 고른다.
• 블랙 레인저는 뒷좌석을 좋아한다. 항상 번호가 가장 큰 행에서 빈 좌석을 고른다. 그 행의 두 좌석이 모두 비어 있으면 왼쪽을 고른다.
• 옐로 레인저도 뒷좌석을 좋아하지만, 가능하면 오른쪽을 고른다.
• 핑크 레인저는 선호가 없어서 아무 좌석이나 고른다.

악당은 k명의 승객 중 누가 각 레인저일 수 있는지 알고 싶어 한다. 일부 레인저는 다른 버스를 탔을 수도 있다.

첫 번째 줄에는 두 정수 n과 k가 주어진다. n은 행의 수, k는 승객의 수이다. (1 ≤ n ≤ 10^9, 1 ≤ k ≤ min(2·10^5, 2n))

다음 k개 줄은 버스에 탄 순서대로 승객을 나타낸다.

i번째 줄에는 두 정수 x_i와 y_i가 주어진다. x_i는 i번째 승객이 고른 행, y_i는 그 행에서 고른 좌석이다. (1 ≤ x_i ≤ n, 1 ≤ y_i ≤ 2) y_i = 1이면 승객이 왼쪽 좌석을 골랐다는 뜻이고, y_i = 2이면 오른쪽 좌석을 골랐다는 뜻이다.

서로 다른 승객의 좌석은 겹치지 않는다.

첫 번째 줄에는 레드 레인저일 수 있는 승객의 수 s_1과, 그 승객들의 번호를 버스에 탄 순서대로 공백으로 구분해 출력한다. 승객에게는 버스에 탄 순서대로 1번부터 k번까지 번호가 붙는다.

다음 네 줄에는 블루 레인저, 블랙 레인저, 옐로 레인저, 핑크 레인저에 대해 같은 정보를 차례대로 출력한다.