Problem Statement

There are $N$ goods stalls numbered from $1$ to $N$. Initially, no one is in line at any goods stall.

There are also $M$ people who buy goods. Each person is assigned one of the numbers $1,2,...,M$, with each number assigned to exactly one person.

From now on, the following $2$ types of events occur a total of $Q$ times, in this order.

• 1 i g Person $i$ joins the end of the line at goods stall $g$. It is guaranteed that immediately before this event occurs, person $i$ is not in line at any goods stall.
• 2 s t The person at the front of the line at goods stall $s$ buys goods 1 time at goods stall $s$, leaves the line, and joins the end of the line at goods stall $t$. It is guaranteed that immediately before this event occurs, at least one person was in line at goods stall $s$.

After the $Q$ events, for each $i=1,2,\dotsc M$, find how many times person $i$ bought goods. Here, assume that no person makes a purchase other than in query 2.

Constraints

• $1\leq N\leq 10^9$
• $1\leq M\leq 10^5$
• $1\leq Q\leq 2\times 10^5$
• In events of type $1$, $1\leq i\leq M$ and $1\leq g\leq N$
• In events of type $2$, $1\leq s,t\leq N$
• All input values are integers

Subtasks

This problem has partial scoring through subtasks.

Input

$N\ M\ Q$
$Query_1$
$Query_2$
$\vdots$
$Query_Q$

Each $Query$ is given in one of the following forms:

$1\ i\ g$

$2\ s\ t$

(one of the above).

Output

Output $M$ lines.

On the $i$-th line, output the number of times person $i$ bought goods.

Sample

9 6 9
1 2 3
1 4 5
2 3 5
2 5 1
1 1 3
1 6 9
2 3 1
2 1 1
2 9 9

1
1
0
2
0
1