AT_arc130_b [ARC130B] Colorful Lines

[problemUrl]: https://atcoder.jp/contests/arc130/tasks/arc130_b $ 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 $ 行で出力してください。

### 制約 - $ 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. ```