Problem H
Shimmer Robots

Silco is currently attempting to create an army of shimmer possessed robots to rule over the world.

Currently, he has plans to make $N$ robots, numbered $1$ to $N$. He has $K$ machines that he can use to create these robots, numbered $1$ to $K$.

He also has a list of $M$ steps to build all of his robots. Each step states that a particular robot requires the given machine performing operation type $\texttt{A}$ or $\texttt{B}$. No robot will require two operations of any type on the same machine.

To build a robot, Silco must perform every operation on the given machine as described by the steps. However, operations of type $\texttt{B}$ will contaminate the machine with shimmer, and operations of type $\texttt{A}$ cannot be performed if the machine is contaminated. Thus, all operations of type $\texttt{A}$ on a machine must be performed before all operations of type $\texttt{B}$. Silco can not partially build a robot, and then switch to building another robot, i.e. Silco must completely build a robot before starting the next one.

Silco wants to figure out if he can make all his robots. Help him find an order to make the robots in, such that all the robots can be created!

Input

The first line contains three space-separated integers $N, M, K (1 \le N, M, K \le 5 \cdot 10^5)$ which represent the number of robots, the number of total steps, and the number of machines, respectively.
Then $M$ lines follow describing the steps that are necessary to build all robots. The $i$-th of these lines contain two integers and a character (all space-separated) $n_i \: (1 \le n_i \le N)$, $k_i \: (1 \le n_i \le K)$, and $c_i \: (c_i \in \{ \texttt{A}, \texttt{B}\} )$. This indicates that robot number $n_i$ requires usage of the machine number $k_i$, and the operation type is $c_i$.

Output

If it is possible to build all the robots, print a single line of $N$ space-separated integers $p_1, p_2, \ldots , p_N$, where $p_i$ is the $i$-th robot made, in order. If there are multiple possible orderings, print any ordering that works. If it is impossible to build all the robots, print a single line, containing the number $-1$.

3 5 5
1 2 B 
1 3 A 
2 1 B 
2 2 A 
3 5 A 

2 1 3 

3 5 3
1 1 A 
1 2 B 
2 1 B 
2 2 A 
3 3 A 

-1