题目描述

题目译自 NordicOI 2019 T2 「Thieves and Prisons」

有 $n$ 个小偷和 $k$ 个监狱。一个小偷要么在逃，要么被关在监狱里。最初，所有小偷都在逃。

一个在逃的小偷可以被警察抓住，然后被关进其中一个监狱。一个监狱里可以有任意数量的小偷。一个在逃的小偷也可以打开一个监狱的门，这样监狱里的所有小偷都会被释放。打开一个空监狱的门是没有意义的，所以这种情况不会发生。

你会得到一个包含 $m$ 个事件的列表，形式为「贼 $x$ 被抓住了」或「贼 $x$ 打开了监狱的门」。你的任务是找到一个对应这些事件的监狱分配方案，或者确定这是不可能的。

输入格式

第一行输入三个整数 $n, k, m$，表示小偷的数量、监狱的数量和事件的数量。小偷和监狱的编号分别为 $1, 2, \dots, n$ 和 $1, 2, \dots, k$。

接下来有 $m$ 行描述这些事件。每个事件是 $\texttt{C x}$（贼 $x$ 被抓住了）或 $\texttt{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

数据范围与提示

详细子任务附加限制及分值如下表所示。