問題文

$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$ 行で出力してください。

入力例 1

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

出力例 1

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.

入力例 2

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

出力例 2

0 5000000000 0