AT_abc346_e [ABC346E] Paint

[problemUrl]: https://atcoder.jp/contests/abc346/tasks/abc346_e $ H $ 行 $ W $ 列のグリッドがあり、はじめすべてのマスは色 $ 0 $ で塗られています。 これから $ i\ =\ 1,\ 2,\ \ldots,\ M $ の順で以下の操作を行います。 - $ T_i\ =\ 1 $ のとき、$ A_i $ **行目**のマスをすべて色 $ X_i $ に塗り替える - $ T_i\ =\ 2 $ のとき、$ A_i $ **列目**のマスをすべて色 $ X_i $ に塗り替える すべての操作を終えたとき、最終的に色 $ i $ で塗られたマスが存在するような各色 $ i $ についてその色で塗られたマスの個数を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ H $ $ W $ $ M $ $ T_1 $ $ A_1 $ $ X_1 $ $ T_2 $ $ A_2 $ $ X_2 $ $ \vdots $ $ T_M $ $ A_M $ $ X_M $

色 $ i $ で塗られたマスが存在するような整数 $ i $ の個数を $ K $ として、$ K\ +\ 1 $ 行出力せよ。 $ 1 $ 行目には $ K $ の値を出力せよ。 $ 2 $ 行目以降には色 $ i $ で塗られたマスが存在するような各色 $ i $ について、色の番号およびその色で塗られたマスの個数を出力せよ。 具体的には、$ i\ +\ 1 $ $ (1\ \leq\ i\ \leq\ K) $ 行目には色の番号 $ c_i $ と色 $ c_i $ で塗られたマスの個数 $ x_i $ をこの順に空白区切りで出力せよ。 ただし、色の番号は**昇順で**出力せよ。すなわち、$ c_1\

### 制約 - $ 1\ \leq\ H,\ W,\ M\ \leq\ 2\ \times\ 10^5 $ - $ T_i\ \in\ \lbrace\ 1,\ 2\ \rbrace $ - $ T_i\ =\ 1 $ なる $ i $ に対して $ 1\ \leq\ A_i\ \leq\ H $ - $ T_i\ =\ 2 $ なる $ i $ に対して $ 1\ \leq\ A_i\ \leq\ W $ - $ 0\ \leq\ X_i\ \leq\ 2\ \times\ 10^5 $ - 入力される値はすべて整数 ### Sample Explanation 1 操作によってグリッドの各マスの色は以下のように変化します。 ``` 0000 0000 0000 0000 0000 0000 → 5555 → 5550 → 5550 → 5550 0000 0000 0000 3333 2222 ``` 最終的に色 $ 0 $ で塗られたマスは $ 5 $ つ、色 $ 2 $ で塗られたマスは $ 4 $ つ、色 $ 5 $ で塗られたマスは $ 3 $ つです。