Switch Configuration for Pipeline Separation

You are tasked with configuring a set of switches to operate valves that control pipelines separating two water reservoirs. Each pipeline has two valves. A pipeline is open if both of its valves are open; otherwise, it is closed. In order to separate the reservoirs, you need every pipeline to be closed (i.e. at least one valve on each pipeline is closed).

Each valve is controlled by one switch. A switch may control multiple valves, and some valves on a pipeline may even be controlled by the same switch. There are two types of control for a valve:

• Normal control: When the switch is closed (state 1), the valve is open; when the switch is open (state 0), the valve is closed.
• Inverted control: When the switch is closed (state 1), the valve is closed; when the switch is open (state 0), the valve is open.

Given the details of which valve is controlled by which switch and its control type for each pipeline, determine whether there exists a configuration of switch states (each being either 0 or 1) that results in all pipelines being closed. If it exists, output any valid configuration of switch states as a binary string (the i-th character corresponds to the state of switch i, where '1' means closed and '0' means open). Otherwise, output IMPOSSIBLE.

Note: This problem can be modeled as a 2-SAT problem. For each pipeline, if the two valves are controlled by switch s₁ and s₂ with types t₁ and t₂ respectively, the condition for the pipeline to be closed is that at least one valve must be closed. For a valve under normal control (t = 0), the valve is closed if the switch is open (state 0); for inverted control (t = 1), the valve is closed if the switch is closed (state 1). Thus, each pipeline gives a clause of the form:

(L₁ ∨ L₂)

where:

• L₁ is ¬x if the first valve is controlled normally or x if inverted (with x representing the boolean variable for that switch where true means closed),
• L₂ is defined similarly for the second valve.

Solve the system of clauses to find a valid assignment of switch states.

inputFormat

The first line contains two integers M and N: the number of switches and the number of pipelines respectively.

Each of the next N lines contains four space-separated integers: s1 t1 s2 t2, where:

• s1 is the index of the switch controlling the first valve, and t1 indicates its control type (0 for normal, 1 for inverted).
• s2 and t2 similarly describe the second valve.

outputFormat

If a valid configuration exists, output a binary string of length M representing the state of each switch (the i-th character is '1' if switch i is closed, '0' if open). If no valid configuration exists, output IMPOSSIBLE.

sample

2 2
1 0 2 0
1 1 2 1

01