配点 : $400$ 点

問題文

$H\times W$ のマス目があります。はじめ、どのマスにも色は塗られていません。

あなたはこのマス目に対して、色を塗っていくことにしました。使うことができる色には、$1, 2, \ldots, C$ の番号で表される $C$ 種類があります。

色を塗る工程が、$Q$ 個のクエリとして与えられます。$i$ 番目のクエリでは整数 $t_i, n_i, c_i$ が与えられ、以下のように色を塗ることを表しています。

• $t_i = 1$ のとき：$n_i$ 行目のマスをすべて色 $c_i$ で塗る。
• $t_i = 2$ のとき：$n_i$ 列目のマスをすべて色 $c_i$ で塗る。

あるマスを色 $c$ で塗ると、そのマスの色は直前の状態によらず常に色 $c$ へ変化します。

色を塗る工程がすべて完了したときに色 $1, 2, \ldots, C$ で塗られているマスの個数を求めてください。

制約

• $2\leq H\leq 10^9$
• $2\leq W\leq 10^9$
• $1\leq C\leq 3\times 10^5$
• $1\leq Q\leq 3\times 10^5$
• $t_i\in \{1,2\}$
• $t_i = 1$ ならば $1\leq n_i\leq H$
• $t_i = 2$ ならば $1\leq n_i\leq W$
• $1\leq c_i\leq C$

入力

入力は以下の形式で標準入力から与えられます。

$H$ $W$ $C$ $Q$

$t_1$ $n_1$ $c_1$

$\vdots$

$t_Q$ $n_Q$ $c_Q$

出力

色 $1, 2, \ldots, C$ で塗られているマスの個数を、空白で区切って $1$ 行で出力してください。

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

0 8 3 3 0 0

色を塗る工程において、マス目の色は次のように変化します。ただし、. はそのマスがどの色でも塗られていないことを意味します。

.....   66666   66666   64666   64626   22222
.....   .....   .....   .4...   .4.2.   .4.2.
.....   .....   33333   34333   34323   34323
.....   .....   .....   .4...   .4.2.   .4.2.

1000000000 1000000000 3 5
1 1 2
1 2 2
1 3 2
1 4 2
1 5 2

0 5000000000 0