AT_abc406_d [ABC406D] Garbage Removal

There is a grid with $ H $ rows and $ W $ columns. Let $ (i, j) $ denote the cell at the $ i $ -th row from the top and the $ j $ -th column from the left. There are $ N $ pieces of trash on the grid; the $ i $ -th piece is at cell $ (X_i, Y_i) $ . You are given $ Q $ queries, which you must process in order. Each query is of one of the following types: - Type $ 1 $ : Given in the format `1 x` in the input. Report the number of trash pieces in the $ x $ -th row. Then, all trash pieces in the $ x $ -th row are removed from the grid. - Type $ 2 $ : Given in the format `2 y` in the input. Report the number of trash pieces in the $ y $ -th column. Then, all trash pieces in the $ y $ -th column are removed from the grid.

The input is given from Standard Input in the following format: > $ H $ $ W $ $ N $ $ X_1 $ $ Y_1 $ $ X_2 $ $ Y_2 $ $ \vdots $ $ X_N $ $ Y_N $ $ Q $ $ \text{query}_1 $ $ \text{query}_2 $ $ \vdots $ $ \text{query}_Q $ Here, $ \text{query}_i $ denotes the $ i $ -th query, which is given in one of the following formats: > $ 1 $ $ x $ > $ 2 $ $ y $

Output $ Q $ lines. The $ i $ -th line should contain the response to the $ i $ -th query.

### Sample Explanation 1 Initially, trash pieces are at cells $ (1, 2), (1, 3), (3, 4), (3, 1), (2, 2) $ . In the 1st query, the 1st row contains two pieces of trash at $ (1, 2) $ and $ (1, 3) $ , so report $ 2 $ . These pieces are then removed; the remaining trash is at $ (3, 4), (3, 1), (2, 2) $ . In the 2nd query, the 2nd row contains one piece of trash at $ (2, 2) $ , so report $ 1 $ . This piece is then removed; the remaining trash is at $ (3, 4), (3, 1) $ . In the 3rd query, the 2nd column contains no trash, so report $ 0 $ . In the 4th query, the 4th column contains one piece of trash at $ (3, 4) $ , so report $ 1 $ . This piece is then removed; the remaining trash is at $ (3, 1) $ . In the 5th query, the 2nd row contains no trash, so report $ 0 $ . ### Constraints - $ 1 \leq H, W, N \leq 2 \times 10^5 $ - $ 1 \leq X_i \leq H $ - $ 1 \leq Y_i \leq W $ - If $ i \neq j $ , then $ (X_i, Y_i) \neq (X_j, Y_j) $ . - $ 1 \leq Q \leq 2 \times 10^5 $ - For a type $ 1 $ query, $ 1 \leq x \leq H $ . - For a type $ 2 $ query, $ 1 \leq y \leq W $ . - All input values are integers.