Problem Description

There is a $n \times n$ chessboard with $k$ pieces, each having a strength value $w_i$.

The rules are as follows:
- The attack range of a piece includes its entire row and column, excluding the piece itself.
- A cell on the board can be attacked if and only if the XOR sum of the strength values of all pieces that can attack it is greater than $0$.

We will perform $p$ operations, and you need to determine the total number of cells that can be attacked after each operation.

Input Format

The first line contains three integers $n, k, p$.

The next $k$ lines each contain three integers $x_i, y_i, w_i$, indicating that there is a piece at position $(x_i, y_i)$ with strength value $w_i$.

The next $p$ lines each contain four integers $r_1, c_1, r_2, c_2$, indicating that the piece at position $(r_1, c_1)$ is moved to position $(r_2, c_2)$.

Output Format

Output $p$ lines, each containing a single integer, representing the total number of cells that can be attacked after the $i$-th operation.

Sample Input and Output

Input Sample #1

2 2 2
1 1 1
2 2 1
2 2 2 1
1 1 1 2

Output Sample #1

4
0

Input Sample #2

2 2 2
1 1 1
2 2 2
2 2 2 1
1 1 1 2

Output Sample #2

4
2

Input Sample #3

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

Output Sample #3

6
7
7
9

Notes

Data Range and Constraints

• For $25\%$ of the data, it is guaranteed that $n, k \le 100$.
• For $100\%$ of the data, it is guaranteed that $1 \le n \le 10^9$, $1 \le k \le 10^5$, $1 \le p \le 10^5$, $1 \le x_i, y_i, r_1, c_1, r_2, c_2 \le n$, $1 \le w_i \le 10^9$, and pieces will not overlap during the moves.

Notes

This problem is worth $120$ points.

This problem is translated from Croatian Open Competition in Informatics 2015/2016 Contest #1 T4 TOPOVI.

见题面 Input 部分

见题面 Output 部分