题目描述

$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$ で塗られているマスの個数を求めてください。

输入格式

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

$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

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

0 5000000000 0

提示

制約

• $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$

Sample Explanation 1

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