Description

After the last failure, Remilia decided to launch the Scarlet Mist incident again. To avoid being exorcised by Reimu, she decided to release the red mist in a strange formation.

We model Gensokyo as an $n \times m$ grid. Initially, no cell is covered by red mist. Each time, Remilia stands on some cell and emits one infinitely long red mist in each of the four cardinal directions, affecting the entire row/column, but not the cell she stands on. If two red mists collide, they settle and disappear due to excessive density. Reimu notices this incident and decides to resolve it. Before that, she wants to know the density of red mist in a rectangular region, which can be summarized as two operations:

1 x y Remilia stands at coordinate $(x, y)$ and releases infinitely long red mist in the four directions.

2 x1 y1 x2 y2 Query the number of cells covered by red mist within the rectangle with top-left $(x_1, y_1)$ and bottom-right $(x_2, y_2)$.

Input Format

The first line contains three integers $n, m, q$, meaning the size of Gensokyo is $n \times m$, and there are $q$ operations.

Then follow $q$ lines. Each line contains $3$ or $5$ integers separated by spaces, as described above.

Output Format

For each operation of type $2$, output one line with one integer representing the answer to that query.

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

8

Hint

Sample Input/Output 1 Explanation

Let o denote no red mist, and x denote red mist. After two releases of red mist, the map of Gensokyo looks like:

oxox
xoxo
oxox
xoxo

Constraints

• For $20\%$ of the testdata, $1 \le n, m, q \le 200$.
• For $40\%$ of the testdata, $1 \le n, m, q \le 10^3$.
• For $100\%$ of the testdata, $1 \le n, m, q \le 10^5$, $1 \le x_1, x_2, x \le n$, $x_1 \le x_2$, $1 \le y_1, y_2, y \le m$, $y_1 \le y_2$.

Translated by ChatGPT 5