Doors

After decades as a software engineer, Seunghwan decided to start a completely different job. While looking through many possibilities, aquaculture caught his attention.

Today is Seunghwan's first day at work. His manager, Gyuhyeon, has already assigned his first task: isolate one reservoir from the others.

Two reservoirs may be connected by several waterways. Each waterway has two doors. If both doors are open, the waterway is open; if at least one of the two doors is closed, the waterway is closed.

Each door is controlled by exactly one switch. A single switch may control many doors, but each door is connected to only one switch. One switch may control both doors of the same waterway, and a switch may also control no doors at all.

The figure above shows a layout with 3 waterways and 2 switches.

A switch controls a door in one of the following two ways.

• When the switch is on, the door is open; when the switch is off, the door is closed.
• When the switch is on, the door is closed; when the switch is off, the door is open.

Given the connections between doors and switches, determine whether it is possible to close every waterway. If it is possible, output whether each switch should be off or on.

The first line contains the number of waterways N (1 <= N <= 250000) and the number of switches M (1 <= M <= 500000).

Each of the next N lines describes one waterway in the form a s_a b s_b. The values a and b (1 <= a, b <= M) are the switch numbers controlling the two doors of that waterway. Each of s_a and s_b is either 0 or 1.

The value s_i has the following meaning.

• If s_i = 0, the corresponding door is closed when switch i is off.
• If s_i = 1, the corresponding door is closed when switch i is on.

If every waterway can be closed, print M lines. On the i-th line, print 0 if switch i should be off, or 1 if it should be on.

If more than one valid configuration exists, you may print any one of them.

If it is impossible to close every waterway, print IMPOSSIBLE.