题目描述

For a grid with each cell colored either white or black, let us define the beauty of the grid as follows:

• Consider performing the following operation any number of times:
  • Choose a path from the upper-left corner to the lower-right corner, consisting only of downward and rightward moves. Invert the colors of all cells on the chosen path.
• The beauty of the grid is defined as the maximum possible number of cells colored black.

You have a grid with $H$ rows and $W$ columns. Initially, all cells are colored white.

You need to process $Q$ queries in order. The $i$-th query is given in the following format:

• You are given two integers $t_i$ and $x_i$.
  • If $t_i = 1$, invert the colors of all cells in the $x_i$-th row from the top.
  • If $t_i = 2$, invert the colors of all cells in the $x_i$-th column from the left.
• Then, find the beauty of the current grid.

输入格式

The input is given in the following format:

$$\begin{aligned} & H \ W \ Q \\ & t_1 \ x_1 \\ & \vdots \\ & t_Q \ x_Q \end{aligned}$$

• $1 \leq H, W \leq 200\ 000$
• $1 \leq Q \leq 200\ 000$
• $t_i \in \{1, 2\}$ ($1 \leq i \leq Q$)
• $t_i = 1 \implies 1 \leq x_i \leq H$ ($1 \leq i \leq Q$)
• $t_i = 2 \implies 1 \leq x_i \leq W$ ($1 \leq i \leq Q$)
• All input values are integers.

输出格式

Output $Q$ lines. On the $i$-th line ($1 \leq i \leq Q$), output the answer for the $i$-th query.

3 4 5
2 2
2 3
1 1
1 2
2 3

9
12
10
10
9