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

在逃的小偷可以被警察抓获，然后被关进其中一个监狱。在逃的小偷也可以打开某个监狱的大门，随后该监狱中的所有小偷都会被释放。打开一个空监狱的大门是没有意义的，因此这种情况永远不会发生。

给你一个包含 $m$ 个事件的列表，事件的形式为“小偷 $x$ 被抓获”或“小偷 $x$ 打开了某个监狱的大门”。你的任务是找到一个与这些事件相对应的监狱分配方案，或者确定这是不可能的。

输入格式

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

接下来的 $m$ 行描述了这些事件。每个事件为 “C x”（小偷 $x$ 被抓获）或 “O x”（小偷 $x$ 打开了某个监狱的大门）。

输出格式

输出一个有效的监狱分配方案，由 $m$ 个整数组成：对于每个事件，输出其对应的监狱编号。如果无解，则输出 “IMPOSSIBLE”。

样例

输入 1

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

输出 1

1 2 2 1 1

输入 2

1 1 1
O 1

输出 2

IMPOSSIBLE

子任务

子任务 1（8 分）

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

子任务 2（13 分）

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

子任务 3（14 分）

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

子任务 4（18 分）

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

子任务 5（47 分）

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