Contest Duration: - (local time) (120 minutes) Back to Home
F - Max Matrix /

Time Limit: 3 sec / Memory Limit: 1024 MB

### 問題文

Q 個のクエリを処理してください。i 個目のクエリでは 3 つの整数 T_i, X_i, Y_i が与えられ、以下の処理をします。

• T_i = 1 のとき : a_{X_i}Y_i に置き換える
• T_i = 2 のとき : b_{X_i}Y_i に置き換える

そして、毎回のクエリの処理直後に \displaystyle \sum_{i = 1}^N \sum_{j = 1}^M \max(a_i, b_j) の値を出力してください。

### 制約

• 1 \le N \le 2 \times 10^5
• 1 \le M \le 2 \times 10^5
• 1 \le Q \le 2 \times 10^5
• T_i1 または 2
• T_i = 1 ならば 1 \le X_i \le N
• T_i = 2 ならば 1 \le X_i \le M
• 1 \le Y_i \le 10^8
• 入力に含まれる値は全て整数である

### 入力

N M Q
T_1 X_1 Y_1
T_2 X_2 Y_2
T_3 X_3 Y_3
\hspace{21pt} \vdots
T_Q X_Q Y_Q


### 入力例 1

2 2 4
1 1 10
2 1 20
2 2 5
1 1 30


### 出力例 1

20
50
55
85


### 入力例 2

3 3 5
1 3 10
2 1 7
1 3 5
2 2 10
2 1 1


### 出力例 2

30
44
31
56
42


### 入力例 3

200000 200000 4
2 112219 100000000
1 73821 100000000
2 26402 100000000
1 73821 100000000


### 出力例 3

20000000000000
39999900000000
59999800000000
59999800000000


Score : 600 points

### Problem Statement

We have a sequence a of length N and a sequence b of length M. Initially, every element in a and b is 0.
You are asked to process Q queries. In the i-th query, given three integers T_i, X_i, and Y_i, do the following:

• if T_i = 1: replace a_{X_i} with Y_i;
• if T_i = 2: replace b_{X_i} with Y_i.

Then, after processing each query, print the value \displaystyle \sum_{i = 1}^N \sum_{j = 1}^M \max(a_i, b_j).

### Constraints

• 1 \le N \le 2 \times 10^5
• 1 \le M \le 2 \times 10^5
• 1 \le Q \le 2 \times 10^5
• T_i is 1 or 2.
• If T_i = 1, 1 \le X_i \le N.
• If T_i = 2, 1 \le X_i \le M.
• 1 \le Y_i \le 10^8
• All values in input are integers.

### Input

Input is given from Standard Input in the following format:

N M Q
T_1 X_1 Y_1
T_2 X_2 Y_2
T_3 X_3 Y_3
\hspace{21pt} \vdots
T_Q X_Q Y_Q


### Output

Print Q integers as instructed in Problem Statement, with newline as separator.

### Sample Input 1

2 2 4
1 1 10
2 1 20
2 2 5
1 1 30


### Sample Output 1

20
50
55
85


If we write \max(a_i, b_j) at the i-th row and j-th column in a grid, the four queries will change it as follows:

### Sample Input 2

3 3 5
1 3 10
2 1 7
1 3 5
2 2 10
2 1 1


### Sample Output 2

30
44
31
56
42


### Sample Input 3

200000 200000 4
2 112219 100000000
1 73821 100000000
2 26402 100000000
1 73821 100000000


### Sample Output 3

20000000000000
39999900000000
59999800000000
59999800000000


The integers to be printed may not fit into a 32-bit integer type.