問題文

$1$ から $N$ までの番号が付けられた $N$ 個のグッズ売り場があります。最初はどのグッズ売り場にも人が並んでいません。

また、グッズを買う人が $M$ 人います。$1,2,...,M$ の番号が各人に一つずつ付けられています。

これから、以下の $2$ 種類のイベントが合計 $Q$ 回、この順で起こります。

• 1 i g 人 $i$ がグッズ売り場 $g$ の最後尾に並ぶ。このイベントが起こる直前に人 $i$ はどのグッズ売り場にも並んでいないことが保証される。
• 2 s t グッズ売り場 $s$ の先頭にいる人がグッズ売り場 $s$ で1回グッズを買って列を抜け、グッズ売り場 $t$ の最後尾に並ぶ。このイベントが起こる直前にグッズ売り場 $s$ には人が一人以上並んでいたことが保証される。

$Q$ 回のイベント後、$i=1,2,\dotsc M$ について、人 $i$ が何回グッズを買ったかを求めてください。ただしどの人もクエリ2以外で買い物はしてないものとします。

制約

• $1\leq N\leq 10^9$
• $1\leq M\leq 10^5$
• $1\leq Q\leq 2\times 10^5$
• $1$ 種類目のイベントにおいて、$1\leq i\leq M$ かつ $1\leq g\leq N$
• $2$ 種類目のイベントにおいて、$1\leq s,t\leq N$
• 入力は全て整数

小課題

この問題にはサブタスクによる部分点が設定されています。

入力

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

また、$Query$ は

$1\ i\ g$

$2\ s\ t$

のいずれかで与えられます。

出力

$M$ 行出力してください。

$i$ 行目には人 $i$ がグッズを買った回数を出力してください。

サンプル

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