Problem Description

Having been a programmer for many years, you are tired of the coding life. You decide to switch careers and do something different.

While searching for your next job, you are attracted by a job in aquaculture. "That's cool!" You think, and since fish are great creatures, you apply without hesitation. Fortunately, you successfully get the offer. Today is your first day at work.

Your boss has assigned you a task: to separate two reservoirs. The operation manual you have been given provides the following information:

There are some pipes connecting the two reservoirs, each pipe having two valves. When both valves are open, the pipe is open; otherwise, it is closed. Valves are controlled by switches. Each switch controls several valves, but each valve is controlled by only one switch. It is possible that both valves on a pipe are controlled by the same switch, or that some switches do not control any valves.

Switches control valves in the following two ways:

• When a switch is closed, the valve opens; when the switch is open, the valve closes.
• When a switch is closed, the valve closes; when the switch is open, the valve opens.

After playing with the switches for a while, you suddenly realize that your programming experience could be very useful. Given which switch controls each valve, determine if it is possible to close all the pipes. If it is possible, find a valid configuration of the states of each switch.

Input Format

The first line of standard input contains two integers $n$ and $m$, representing the number of pipes and the number of switches, respectively. Switches are numbered from $1$ to $m$.

The next $n$ lines describe the pipes, with each line containing four integers $a, s_a, b, s_b$ describing a pipe. $a$ and $b$ represent the switches controlling the pipe ($1 \le a, b \le m$). $s_a$ and $s_b$ are either $0$ or $1$, corresponding to the operation modes described, where $s_i=0$ means the valve closes if and only if switch $i$ is open, and $s_i=1$ means the valve closes if and only if switch $i$ is closed.

Output Format

If it is possible to close all the pipes, the standard output should contain $m$ lines. The $i$-th line should output $0$ if switch $i$ is open, and $1$ if switch $i$ is closed. If there are many possible answers, your program can output any one of them.

If it is impossible to close all the pipes, your program should output one line containing the word IMPOSSIBLE.

Sample Input and Output

Sample Input #1

3 2
1 0 2 1
1 0 2 0
1 1 2 1

Sample Output #1

0
1

Sample Input #2

2 1
1 0 1 0
1 1 1 1

Sample Output #2

IMPOSSIBLE

Notes

Data Range

For $30\%$ of the data, $n \le 40, m \le 20$.

For all data, $1 \le n \le 2.5 \times 10^5, 1 \le m \le 5 \times 10^5$.

见题面 Input 部分

见题面 Output 部分