In the event of technical difficulties with Szkopuł, please contact us via email at firstname.lastname@example.org.
If you are familiar with IRC chat, the support team is also reachable on PIRC network (
#szkopul channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
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.
Example with three channels and two switches.
The switch may operate the gate in one of two ways:
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.
The first line of the standard input contains two integers and , the number of channels and switches respectively. Switches are numbered from to . Additionally, in test cases worth at least points, will not exceed and will not exceed .
The following lines describe channels, each channel is described by a separate line containing four integers: , , , . Numbers and represent switches () that operate gates of this channel. Numbers and can be either or and correspond to the described operation modes: means that the gate is closed if and only if the switch is off and means that the gate is closed if and only if the switch is on.
If it is possible to close all the channels, the standard output should contain lines. Line should contain , if switch should be off, and if switch 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.
For the input data:
3 2 1 0 2 1 1 0 2 0 1 1 2 1
the correct result is:
and for the input data:
2 1 1 0 1 0 1 1 1 1
the correct result is:
The first example corresponds to the picture from the task description.
Task author: Linas Petrauskas.