题目描述

接近一百人参与使 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$ 、$l$ 和 $r$ （$1 \le p \le n$，$0 \le l < r \le 10^9$ ），描述一次旅行，其中人员 $p$ 在时间 $l$ 离开，在时间 $r$ 返回。

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

保证对于每个人，他们的旅行不会接触或重叠。

输出格式

如果可能分配钥匙使得没有人被锁在门外，输出一个长度为 $q$ 的字符串，其中每个字符是 0 或 1 。如果进行第 $i$ 次旅行（按输入顺序）的人应该随身带一把钥匙，则字符串的第 $i$ 个字符是 1 。否则，输出 0。 如果有多个有效解决方案，你可以输出其中任意一个。

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

01110

2 1 2
1 2 4
2 1 3

01

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

impossible