{"problem":{"name":"Max Matrix","description":{"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$.   You are asked to process $Q$ queries. In the $i$\\-th query, given three integer","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"jsc2021_f"},"statements":[{"statement_type":"Markdown","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)$.\n\n## Constraints\n\n*   $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.\n\n## Input\n\nInput 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$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"jsc2021_f","tags":[],"sample_group":[["2 2 4\n1 1 10\n2 1 20\n2 2 5\n1 1 30","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)"],["3 3 5\n1 3 10\n2 1 7\n1 3 5\n2 2 10\n2 1 1","30\n44\n31\n56\n42"],["200000 200000 4\n2 112219 100000000\n1 73821 100000000\n2 26402 100000000\n1 73821 100000000","20000000000000\n39999900000000\n59999800000000\n59999800000000\n\nThe integers to be printed may not fit into a $32$\\-bit integer type."]],"created_at":"2026-03-03 11:01:14"}}