题目描述

题目译自 BalticOI 2008 Day1「Gates」

成为码农多年的你，已经厌倦了码农生活。你决定跳槽，去做一些不一样的事情。
正在寻找下一份工作的你，被一份水产养殖的工作吸引住了。“太酷了！”并且，鱼是很好的生物 嗯切绘也是这么想的 。所以你毫不犹豫地去应聘了。幸运的是，你成功拿到了 Offer。今天是你工作的第一天。
你的老板已经给你分配了任务：分隔两个蓄水池。你手上的操作指南告诉了你如下信息：
这两个蓄水池之间有一些管道连通，每个管道有两个阀门。当两个阀门同时开启时，这个管道就处于开启状态，反之处于关闭状态。阀门用开关控制。同一个开关会控制一些阀门，但是每一个阀门都只被一个开关控制。有可能一个管道上的两个阀门被同一个开关控制，也可能有开关不控制任何阀门。

开关以以下两种方式控制阀门：

• 当开关闭合时阀门打开，当开关断开时阀门关闭
• 当开关闭合时阀门关闭，当开关断开时阀门打开

玩了一会儿开关之后你突然意识到你的编程经历会十分有用。给出每个阀门被哪个开关所控制，判断是否可能关闭所有管道，如果可以，找出这种合法配置下每一个开关的状态。

输入格式

标准输入的第一行包含两个整数 $n$ 和 $m$，分别表示管道数和开关数。开关被从 $1$ 到 $m$ 标号。
接下来的 $n$ 行描述管道，一行用四个整数 $a,s_a,b,s_b$ 描述一个管道，$a,b$ 代表控制该管道的开关（$1\le a,b\le m$）。$s_a$ 和 $s_b$ 为 $0$ 或 $1$，并与描述中的操作模式相符，$s_i=0$ 表示当且仅当开关 $i$ 断开时阀门关闭，$s_i=1$ 表示当且仅当开关 $i$ 闭合时阀门关闭。

输出格式

如果有可能关闭所有管道，标准输出应包含 $m$ 行，如果开关 $i$ 断开，第 $i$ 行应输出 $0$，如果开关 $i$ 闭合，第 $i$ 行应输出 $1$。如果有很多可能的答案，你的程序可以输出任意一种。
如果不可能关闭所有管道，你的程序应输出一行，包含一个单词 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

数据范围与提示

对于 $30\%$ 的数据，$n\le 40, m\le 20$。
对于所有数据，$1\le n\le 2.5\times 10^5, 1\le m\le 5\times 10^5$。