K. 公寓钥匙

Juggling Keys

时间限制：5 秒 · 内存限制：1024 MiB

原题：NWERC 2025 J · 查看官方英文原文（英文 PDF 也已作为本题附件提供）

题目描述

$n$ 个人共住一间公寓，一共有 $k$ 把钥匙。已知全部 $q$ 次外出的人员、离开时间和返回时间。你需要决定每次外出的人是否带上一把钥匙。钥匙随外出的人离开，并在此人回来时带回公寓。

当一个人回来时，如果公寓里还有其他人，就可以按门铃让对方开门；如果公寓里没有其他人，这个人必须自己携带钥匙，否则就会被锁在门外。每次出发时，也必须有可供携带的钥匙，不能使用仍被其他外出者携带的钥匙。

请为所有外出安排是否带钥匙，使每个人都能按时进入公寓，或判断不存在这样的安排。

输入格式

第一行包含 $n$、$k$、$q$（$1 \leq k \leq n \leq 100000$，$1 \leq q \leq 100000$）。

随后 $q$ 行，每行包含 $p$、$l$、$r$（$1 \leq p \leq n$，$0 \leq l < r \leq 10^{9}$），表示第 $p$ 个人在 $l$ 时刻离开，在 $r$ 时刻返回。

任一时刻至多发生一次离开或返回。同一个人的外出时间段不会相交，也不会端点相接。第一次外出前所有人及所有钥匙都在公寓中。

输出格式

如果存在合法安排，输出长度为 $q$、只包含 $0$ 和 $1$ 的字符串。第 $j$ 个字符对应输入中的第 $j$ 次外出：$1$ 表示带一把钥匙，$0$ 表示不带钥匙。

如果不存在合法安排，输出 impossible。有多个合法安排时输出任意一个即可。

样例

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

原题版权归原作者及相应赛事评委会所有，采用 CC BY-SA 4.0 许可。中文译文为本练习赛整理，按相同许可发布。题号及中文标题作了调整，输入约束、样例和判题要求依照官方原题；图示及完整英文叙述请参阅英文原文附件。