{"raw_statement":[{"iden":"problem statement","content":"We have a sequence $a$ of length $N$ and a sequence $b$ of length $M$. Initially, every element in $a$ and $b$ is $0$.  \nYou are asked to process $Q$ queries. In the $i$\\-th query, given three integers $T_i$, $X_i$, and $Y_i$, do the following:\n\n*   if $T_i = 1$: replace $a_{X_i}$ with $Y_i$;\n*   if $T_i = 2$: replace $b_{X_i}$ with $Y_i$.\n\nThen, after processing each query, print the value $\\displaystyle \\sum_{i = 1}^N \\sum_{j = 1}^M \\max(a_i, b_j)$."},{"iden":"constraints","content":"*   $1 \\le N \\le 2 \\times 10^5$\n*   $1 \\le M \\le 2 \\times 10^5$\n*   $1 \\le Q \\le 2 \\times 10^5$\n*   $T_i$ is $1$ or $2$.\n*   If $T_i = 1$, $1 \\le X_i \\le N$.\n*   If $T_i = 2$, $1 \\le X_i \\le M$.\n*   $1 \\le Y_i \\le 10^8$\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $M$ $Q$\n$T_1$ $X_1$ $Y_1$\n$T_2$ $X_2$ $Y_2$\n$T_3$ $X_3$ $Y_3$\n$\\hspace{21pt} \\vdots$\n$T_Q$ $X_Q$ $Y_Q$"},{"iden":"sample input 1","content":"2 2 4\n1 1 10\n2 1 20\n2 2 5\n1 1 30"},{"iden":"sample output 1","content":"20\n50\n55\n85\n\nIf 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: ![image](https://img.atcoder.jp/ghi/9a4098e2aa50b21c51ce3664d278ba87.png)"},{"iden":"sample input 2","content":"3 3 5\n1 3 10\n2 1 7\n1 3 5\n2 2 10\n2 1 1"},{"iden":"sample output 2","content":"30\n44\n31\n56\n42"},{"iden":"sample input 3","content":"200000 200000 4\n2 112219 100000000\n1 73821 100000000\n2 26402 100000000\n1 73821 100000000"},{"iden":"sample output 3","content":"20000000000000\n39999900000000\n59999800000000\n59999800000000\n\nThe integers to be printed may not fit into a $32$\\-bit integer type."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}