背景

Special Judge 来自于 LibreOJ。

题目描述

有 $n$ 个盗贼和 $k$ 座监狱。一个盗贼要么正在逃亡，要么已被关押在某座监狱中。初始时，所有盗贼都在逃亡。

一个正在逃亡的盗贼可以被警察抓住，随后被关进其中一座监狱。一个正在逃亡的盗贼也可以打开某座监狱的大门。当大门被打开时，关押在该监狱中的所有盗贼都会被释放。打开一座空监狱的大门是毫无意义的，因此这种情况永远不会发生。

你得到一个包含 $m$ 个事件的列表，事件的格式为“盗贼 $x$ 被抓住”或“盗贼 $x$ 打开了某座监狱的大门”。你的任务是找出一个符合这些事件的监狱分配方案，或者判断这是不可能的。

输入格式

第一行输入包含三个整数 $n$、$k$ 和 $m$：分别表示盗贼的数量、监狱的数量以及事件的数量。盗贼和监狱的编号分别为 $1, 2, \ldots, n$ 和 $1, 2, \ldots, k$。

此后是 $m$ 行，描述各个事件。每个事件是“C $x$”（盗贼 $x$ 被抓住）或“O $x$”（盗贼 $x$ 打开了某座监狱的大门）。

输出格式

输出一个有效的监狱分配方案，由 $m$ 个整数组成：每个整数对应相应事件所涉及的监狱。如果不存在解决方案，则输出“IMPOSSIBLE”。

3 2 5
C 1
C 2
O 3
O 2
C 1

1 2 2 1 1

1 1 1
O 1

IMPOSSIBLE

提示

子任务 1（8 分）

• $1 \leq n, m \leq 10$
• $k = 2$

子任务 2（13 分）

• $1 \leq n, k, m \leq 10^5$
• $n = k$

子任务 3（14 分）

• $1 \leq n, m \leq 10^5$
• $k = 2$

子任务 4（18 分）

• $1 \leq n, k, m \leq 500$

子任务 5（47 分）

• $1 \leq n, k, m \leq 10^5$

翻译由 DeepSeek V3 完成