 Code Submission Evaluation System Login

# NOI 2019 Open

 Start: N/A End: N/A

CSES - NOI 2019 Open - Thieves and PrisonsCSES - Thieves and Prisons

## Thieves and Prisons

 Time limit: 1.00 s Memory limit: 512 MB

There are $n$ thieves and $k$ prisons. A thief is either on the run or caught in a prison. Initially all thieves are on the run.

A thief who is on the run can be caught by the police, and then ends up in one of the prisons. A thief who is on the run can also open the gate of a prison. Then every thief in that prison is released from the prison. It would be pointless to open the gate of an empty prison, so that never happens.

You are given a list of $m$ events of the form "thief $x$ has been caught" or "thief $x$ has opened the gate of a prison". Your task is to find a prison assignment that corresponds to the events, or determine that it is not possible.

Input

The first input line has three integers $n$, $k$ and $m$: the number of thieves, prisons and events. The thieves and prisons are numbered $1,2,\dots,n$ and $1,2,\dots,k$.

After this, there are $m$ lines that describe the events. Each event is "C $x$" (thief $x$ has been caught) or "O $x$" (thief $x$ opens the gate of a prison).

Output

Print a valid prison assignment that consists of $m$ integers: for every event the corresponding prison. If there are no solutions, print "IMPOSSIBLE".

Example 1

Input:
3 2 5 C 1 C 2 O 3 O 2 C 1

Output:
1 2 2 1 1

Example 2

Input:
1 1 1 O 1

Output:
IMPOSSIBLE

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