Baltic Olympiad in Informatics: 2008 Day 1, Problem 2

After many years of working as a software developer you have decided to try something entirely different, and started looking at random job offers. The one that really caught your eye was a job in fish farming (a form of aquaculture). 'Cool!', you thought, and besides, fish are nice creatures. So you applied, got accepted, and today is your first day at work.

Your boss has already assigned you a task. You have to isolate one water reservoir from another. After looking at some schemes you've been given, here's what you've figured out.

The two water reservoirs are connected by several channels. Each channel has two gates. The channel is open when both gates are open, and is closed otherwise. The gates are controlled using switches. The same switch may operate several gates, but each gate is operated by exactly one switch. It is possible that both gates on a channel are controlled by the same switch and that a switch controls no gates.

The switch may operate the gate in one of two ways:

• the gate is open when the switch is on, and is closed when the switch is off

• the gate is closed when the switch is on, and is open when the switch is off

After playing a bit with the switches you suddenly realize that your programming experience will come in very handy. Write a program that, given the configuration of gates and switches, determines whether it is possible to close all channels, and if it is, then finds a state of every switch in one such valid configuration.

Constraints

~1 \le n \le 250\,000~

~1 \le m \le 5 \times 10^5~

Subtask 1 [30%]

~1 \le n \le 40~

~1 \le m \le 20~

Subtask 2 [70%]

No additional constraints.

Input Specification

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

The following ~n~ lines describe channels, each channel is described by a separate line containing four integers: ~a~, ~s_a~, ~b~, ~s_b~. Numbers ~a~ and ~b~ represent switches ~(1 \le a,b \le m)~ that operate gates of this channel. Numbers ~s_a~ and ~s_b~ can be either 0 or 1 and correspond to the described operation modes: ~s_i = 0~ means that the gate is closed if and only if the switch ~i~ is off, and ~s_i = 1~ means that the gate is closed if and only if the switch ~i~ is on.

Output Specification

If it is possible to close all the channels, the standard output should contain ~m~ lines. Line ~i~ should contain 0, if switch ~i~ should be off, and 1 if switch ~i~ should be on. If there are many possible solutions, your program may output any of them.

If it is impossible to close all channels, your program should output one line, containing a single word IMPOSSIBLE.

Sample Input 1

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

Sample Output 1

0
1

Explanation for Sample 1

This sample corresponds to the picture from the task description.

Sample Input 2

2 1
1 0 1 0
1 1 1 1

Sample Output 2

IMPOSSIBLE