Description

After being a programmer for many years, you have gotten tired of the programmer’s life. You decide to change jobs and do something different.

While looking for your next job, you are attracted by a job in aquaculture. “So cool!” And fish are great creatures. So you apply without hesitation. Luckily, you get an offer. Today is your first day at work. Your boss has assigned you a task: separate two water reservoirs.

The manual you have tells you the following information:

There are some pipes connecting the two reservoirs. Each pipe has two valves. A pipe is open when both valves are open at the same time; otherwise it is closed. Valves are controlled by switches. The same switch controls some valves, but each valve is controlled by exactly one switch. It is possible that the two valves on a pipe are controlled by the same switch, and it is also possible that some switches control no valves.

A switch controls a valve in one of the following two ways:

• When the switch is closed, the valve opens; when the switch is open, the valve closes.
• When the 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 will be very useful. Given which switch controls each valve, determine whether it is possible to close all pipes. If it is, find the state of every switch in such a valid configuration.

Input Format

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

The next $n$ lines describe the pipes. Each line contains four integers $a, s_a, b, s_b$ describing one pipe. $a, b$ are the switches controlling the pipe ($1 \le a, b \le m$). $s_a$ and $s_b$ are $0$ or $1$ and correspond to the control modes in the description: $s_i = 0$ means the valve is closed if and only if switch $i$ is open, and $s_i = 1$ means the valve is closed if and only if switch $i$ is closed.

Output Format

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

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

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

0
1

2 1
1 0 1 0
1 1 1 1

IMPOSSIBLE

Hint

Constraints

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

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

Translated by ChatGPT 5