将近一百人参与了 NWERC 的举办——组织者、志愿者、裁判、系统与直播团队，当然还有负责评测系统的 DOMjudge 团队。他们每次都会来到 NWERC，并且在这里度过非常愉快的时光！

DOMjudge 团队成员喜欢在 NWERC 期间合租一套公寓，但通常钥匙的数量不够每个人都分到一把。这会让后勤变得有些棘手：有些人喜欢早起去吃早餐，有些人则在圣诞集市逗留到很晚，还有些人可能会在下午回公寓短暂小憩。如果有人在公寓里还有其他人时返回，他们只需按门铃即可被放进去。然而，如果有人在公寓空无一人时返回，他们就必须随身携带一把钥匙。

给定每个人外出旅行的时间，请确定每个人在每次出行时是否应该携带钥匙，以便所有人都能顺利进入公寓而不会被（暂时）锁在门外。

图 J.1：样例输入 1 的图解。有 3 名 DOMjudge 团队成员，2 把钥匙，共 5 次出行。携带钥匙的出行用粗线表示。有两次有人回到空无一人的房屋，必须使用钥匙开门。

输入格式

输入包含：

• 第一行包含三个整数 $n$、$k$ 和 $q$（$1 \le k \le n \le 10^5$，$1 \le q \le 10^5$），分别表示 DOMjudge 团队成员的数量、钥匙的数量以及出行的总次数。
• 接下来的 $q$ 行，每行包含三个整数 $p$、$\ell$ 和 $r$（$1 \le p \le n$，$0 \le \ell < r \le 10^9$），描述一次出行：成员 $p$ 在时间 $\ell$ 离开，并在时间 $r$ 返回。

在任何时刻，最多只有一个人到达或离开。

保证对于每个人，他们所进行的出行在时间上不会接触或重叠。

输出格式

如果可以合理分配钥匙使得没有人被锁在门外，输出一个长度为 $q$ 的字符串，其中每个字符为 '0' 或 '1'。如果第 $i$ 次出行（按输入顺序）的成员应该携带钥匙，则字符串的第 $i$ 个字符为 '1'，否则为 '0'。如果无解，输出 "impossible"。

如果存在多个可行解，你可以输出其中任意一个。

样例

输入样例 1

3 2 5
3 0 9
1 2 18
2 4 7
3 12 22
2 14 20

输出样例 1

01110

输入样例 2

2 1 2
1 2 4
2 1 3

输出样例 2

01

输入样例 3

2 1 3
1 1 5
2 2 3
2 4 6

输出样例 3

impossible