Thao tác trên ma trận

Time limit: 1.0s , Memory limit: 256M , Points: 2500 (partial)

Cho mảng $a$ ~a~ gồm $n$ ~n~ phần tử được đánh số từ $1$ ~1~ đến $n$ ~n~ và mảng $b$ ~b~ gồm $m$ ~m~ phần tử được đánh số từ $1$ ~1~ đến $m$ ~m~.

Cho ma trận $X$ ~X~ kích thước $n \times m$ ~n \times m~. Mỗi phần tử $X_{i,j}$ ~X_{i,j}~ $(1 \le i \le n$ ~(1 \le i \le n~, $1 \le j \le m)$ ~1 \le j \le m)~ của ma trận được tính như sau:

$X_{i,j}=max(a_i,b_j)$

Ví dụ, với $a=[1,4,2]$ ~a=[1,4,2]~ và $b=[6,0,3,2]$ ~b=[6,0,3,2]~, ma trận $X$ ~X~ được xây dựng như sau:

$X = \left( \begin{array}{cc} max(a_1,b_1) & max(a_1,b_2) & max(a_1,b_3) & max(a_1,b_4)\\ max(a_2,b_1) & max(a_2,b_2) & max(a_2,b_3) & max(a_2,b_4)\\ max(a_3,b_1) & max(a_3,b_2) & max(a_3,b_3) & max(a_3,b_4) \end{array} \right) = \left( \begin{array}{cc} 6 & 1 & 3 & 2\\ 6 & 4 & 4 & 4\\ 6 & 2 & 3 & 2 \end{array} \right)$

Ban đầu, mọi phần tử của cả hai mảng $a$ ~a~ và $b$ ~b~ đều có giá trị $0$ ~0~, hay nói cách khác, $a_i=0$ ~a_i=0~ với mọi $1 \le i \le n$ ~1 \le i \le n~ và $b_j=0$ ~b_j=0~ với mọi $1 \le j \le m$ ~1 \le j \le m~.

Thực hiện $k$ ~k~ thao tác thuộc một trong hai loại sau trên ma trận:

Loại $1$ ~1~ có dạng 1 x y $(1 \le x \le n)$ ~(1 \le x \le n)~: Gán $a_x=y$ ~a_x=y~ và tính toán lại các giá trị $X_{i,j}$ ~X_{i,j}~ của ma trận.
Loại $2$ ~2~ có dạng 2 x y $(1 \le x \le m)$ ~(1 \le x \le m)~: Gán $b_x=y$ ~b_x=y~ và tính toán lại các giá trị $X_{i,j}$ ~X_{i,j}~ của ma trận.

Với mỗi thao tác sau khi thực hiện, yêu cầu tính tổng giá trị các phần tử của ma trận $X$ ~X~, hay nói cách khác, yêu cầu tính:

$\displaystyle \sum_{i=1}^{n}\sum_{j=1}^{m}X_{i,j}$

Input

Dòng đầu tiên chứa ba số nguyên $n,m,k$ ~n,m,k~ $(1 \le n,m,k \le 2 \times 10^5)$ ~(1 \le n,m,k \le 2 \times 10^5)~.
$k$ ~k~ dòng tiếp theo, mỗi dòng chứa ba số nguyên $t,x,y$ ~t,x,y~ mô tả thao tác thuộc một trong hai loại trên $(t \in \{1,2\}$ ~(t \in \{1,2\}~ $;$ ~;~ $1 \le y \le 10^8)$ ~1 \le y \le 10^8)~.

Output

Với mỗi thao tác sau khi thực hiện, in ra tổng giá trị các phần tử của ma trận $X$ ~X~.

Examples

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

Scoring

Subtask $1$ ~1~ $-$ ~-~ $500$ ~500~ điểm: $n,m,k \le 100$ ~n,m,k \le 100~
Subtask $2$ ~2~ $-$ ~-~ $750$ ~750~ điểm: $n,m,k \le 2000$ ~n,m,k \le 2000~
Subtask $3$ ~3~ $-$ ~-~ $750$ ~750~ điểm: $y \le 10^6$ ~y \le 10^6~ với mọi thao tác
Subtask $4$ ~4~ $-$ ~-~ $500$ ~500~ điểm: Không có ràng buộc gì thêm

Notes

Trong ví dụ thứ nhất, ban đầu $a=[0,0,0]$ ~a=[0,0,0]~ và $b=[0,0,0,0]$ ~b=[0,0,0,0]~. Ở thao tác đầu tiên, gán $a_1=1$ ~a_1=1~, khi đó $a=[1,0,0]$ ~a=[1,0,0]~ và $b=[0,0,0,0]$ ~b=[0,0,0,0]~. Ma trận $X$ ~X~ được xây dựng như sau:

$X = \left( \begin{array}{cc} max(a_1,b_1) & max(a_1,b_2) & max(a_1,b_3) & max(a_1,b_4)\\ max(a_2,b_1) & max(a_2,b_2) & max(a_2,b_3) & max(a_2,b_4)\\ max(a_3,b_1) & max(a_3,b_2) & max(a_3,b_3) & max(a_3,b_4) \end{array} \right) = \left( \begin{array}{cc} 1 & 1 & 1 & 1\\ 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 \end{array} \right)$

Tổng các phần tử ma trận là $4$ ~4~.

Ở thao tác thứ hai, gán $b_1=6$ ~b_1=6~, khi đó $a=[1,0,0]$ ~a=[1,0,0]~ và $b=[6,0,0,0]$ ~b=[6,0,0,0]~. Ma trận $X$ ~X~ được xây dựng như sau:

$X = \left( \begin{array}{cc} max(a_1,b_1) & max(a_1,b_2) & max(a_1,b_3) & max(a_1,b_4)\\ max(a_2,b_1) & max(a_2,b_2) & max(a_2,b_3) & max(a_2,b_4)\\ max(a_3,b_1) & max(a_3,b_2) & max(a_3,b_3) & max(a_3,b_4) \end{array} \right) = \left( \begin{array}{cc} 6 & 1 & 1 & 1\\ 6 & 0 & 0 & 0\\ 6 & 0 & 0 & 0 \end{array} \right)$

Tổng các phần tử ma trận là $21$ ~21~.