Description

There is an $n \times n$ chessboard with $k$ pieces on it. Each piece has a power value $w_i$.

We define the following rules:

• The attack range of a piece is the row and the column it is in, excluding its own cell.
• A cell on the board is considered attacked if and only if the XOR sum of the power values of all pieces that can attack it is greater than $0$.

Now we will perform $p$ operations. After each operation, output the total number of cells that are attacked.

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$. The $i$-th line means there is a piece at position $(x_i,y_i)$ with power value $w_i$.

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

Output Format

Output $p$ lines. Each line contains one integer. The $i$-th line is the total number of cells that are attacked after the $i$-th operation.

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

4
0 

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

4
2

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 

6
7
7
9

Hint

Constraints

• For $25\%$ of the testdata, $n,k \le 100$.
• For $100\%$ of the testdata, $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$. During movements, pieces will not overlap.

Notes

This problem is worth 120 points.

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

Translated by ChatGPT 5