문

수십 년 동안 소프트웨어 엔지니어로 일해 온 승환이는 이제 전혀 다른 일을 시작하기로 했다. 여러 일자리를 살펴보던 중 그의 눈길을 사로잡은 직업은 양식업이었다.

오늘은 승환이가 처음 출근한 날이다. 상사 규현이는 승환이가 맡을 일을 이미 정해 두었다. 승환이는 저수지 하나를 다른 저수지들과 격리해야 한다.

두 저수지는 여러 개의 수로로 연결되어 있다. 각 수로에는 문이 두 개 있다. 두 문이 모두 열려 있으면 그 수로는 열린 상태이고, 둘 중 하나라도 닫혀 있으면 그 수로는 닫힌 상태이다.

각 문은 스위치 하나로 작동한다. 하나의 스위치가 여러 문을 작동시킬 수 있지만, 각 문은 정확히 하나의 스위치에만 연결된다. 한 스위치가 같은 수로의 두 문을 모두 작동시키는 경우도 가능하며, 어떤 문에도 연결되지 않은 스위치가 있을 수도 있다.

위 그림은 수로 3개와 스위치 2개가 있는 배치를 보여 준다.

스위치는 문을 다음 두 방식 중 하나로 작동시킨다.

• 스위치가 켜져 있으면 문이 열리고, 꺼져 있으면 문이 닫힌다.
• 스위치가 켜져 있으면 문이 닫히고, 꺼져 있으면 문이 열린다.

문과 스위치의 연결 정보가 주어졌을 때, 모든 수로를 닫을 수 있는지 판별하라. 가능하다면 각 스위치를 꺼야 하는지 켜야 하는지도 출력하라.

첫째 줄에 수로의 개수 N (1 <= N <= 250000)과 스위치의 개수 M (1 <= M <= 500000)이 주어진다.

다음 N개의 줄에는 각 수로의 정보가 a s_a b s_b 형식으로 주어진다. a와 b (1 <= a, b <= M)는 그 수로의 두 문을 각각 작동시키는 스위치 번호이다. s_a와 s_b는 각각 0 또는 1이다.

값 s_i의 의미는 다음과 같다.

• s_i = 0이면 스위치 i가 꺼져 있을 때 해당 문이 닫힌다.
• s_i = 1이면 스위치 i가 켜져 있을 때 해당 문이 닫힌다.

모든 수로를 닫을 수 있다면 M개의 줄을 출력한다. i번째 줄에는 스위치 i를 꺼야 하면 0, 켜야 하면 1을 출력한다.

가능한 상태가 여러 개라면 아무거나 출력해도 된다.

모든 수로를 닫을 수 없다면 IMPOSSIBLE을 출력한다.