Problem Statement

We will paint $N^2$ tiles arranged in $N$ rows and $N$ columns. There are $K$ colors, numbered from $1$ to $K$, and initially all tiles are painted in color $1$. A total of $Q$ painting operations are performed. In the $i$-th operation, if $A_i$ is "R", all tiles in row $B_i$ are repainted, and if it is "C", all tiles in column $B_i$ are repainted, with color $C_i$. Find how many tiles of each color there are in the end.

Input

$N$ $K$ $Q$
$A_1$ $B_1$ $C_1$
$\vdots$
$A_Q$ $B_Q$ $C_Q$

All input values except $A_i$ ($1 \leq i \leq Q$) are integers, and the input satisfies the following constraints.
$1 \leq N \leq 10^5$
$1 \leq K \leq 10^5$
$1 \leq Q \leq 10^5$
$A_i$ is "R" or "C" ($1 \leq i \leq Q$)
$1 \leq B_i \leq N$ ($1 \leq i \leq Q$)
$1 \leq C_i \leq K$ ($1 \leq i \leq Q$)

Output

On line $i$, print the number of tiles that end up in color $i$ ($1 \leq i \leq K$). Print a newline at the end of every line, including the last line.

Sample

3 4 6
C 1 2
C 2 3
R 2 1
C 3 4
R 3 3
C 2 1

4
1
2
2

1 5 2
R 1 4
R 1 4

0
0
0
1
0

100000 2 1
R 12345 2

9999900000
100000