在作为软件开发人员工作多年后，你决定尝试一些完全不同的事情，并开始随机浏览招聘启事。其中一个真正吸引你眼球的是一份在养鱼场（水产养殖的一种形式）的工作。“酷！”你心想，而且鱼也是很可爱的生物。于是你申请了，被录取了，而今天是你上班的第一天。

你的老板已经给你分配了一个任务。你必须将一个蓄水池与另一个蓄水池隔离开来。在查看了给你的一些图纸后，你理清了以下情况。

这两个蓄水池由几条通道连接。每条通道有两个闸门。当两个闸门都打开时，通道处于打开状态；否则，通道处于关闭状态。闸门由开关控制。同一个开关可以控制多个闸门，但每个闸门恰好由一个开关控制。通道上的两个闸门有可能由同一个开关控制，也可能存在不控制任何闸门的开关。

拥有三条通道和两个开关的示例。

开关可以通过以下两种方式之一来控制闸门：

• 当开关处于开启（on）状态时闸门打开，当开关处于关闭（off）状态时闸门关闭；
• 当开关处于开启（on）状态时闸门关闭，当开关处于关闭（off）状态时闸门打开。

在摆弄了一会儿开关之后，你突然意识到你的编程经验将派上大用场。编写一个程序，在给定闸门和开关的配置情况下，确定是否可能关闭所有通道，如果可以，则找到一种可行配置下每个开关的状态。

输入格式

输入的第一行包含两个整数 $n$（$1 \le n \le 250\,000$）和 $m$（$1 \le m \le 500\,000$），分别表示通道的数量和开关的数量。开关从 $1$ 到 $m$ 编号。此外，在价值至少 30% 分数的测试用例中，$n$ 不超过 40 且 $m$ 不超过 20。

接下来的 $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$ 行应包含 0（如果开关 $i$ 应该关闭）或 1（如果开关 $i$ 应该开启）。如果存在多种可能的解决方案，你的程序可以输出其中任意一种。

如果无法关闭所有通道，你的程序应输出一行，包含单个单词 IMPOSSIBLE。

样例

输入样例 1

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

输出样例 1

0
1

输入样例 2

2 1
1 0 1 0
1 1 1 1

输出样例 2

IMPOSSIBLE

说明

第一个样例对应题目描述中的插图。