OpenKattis
National University of Singapore

# Topovi

Mirko is a huge fan of chess and programming, but typical chess soon became boring for him, so he started having fun with rook pieces.

He found a chessboard with $N$ rows and $N$ columns and placed $K$ rooks on it. Mirko’s game is made of the following rules:

1. Each rook’s power is determined by an integer.

2. A rook sees all the fields that are in his row or column except its own field.

3. We say that a field is attacked if the binary XOR of all the powers of the rooks that see the field is greater than $0$.

Notice that the field a rook is at can be attacked or not.

Initially, Mirko placed the rooks in a certain layout on the board and will make $P$ moves. After each move, determine how many fields are attacked. Every rook can be moved to any free field on the whole board (not only across column and row).

## Input

The first line of input contains integers $N$, $K$, $P$ ($1 \leq N \leq 1\ 000\ 000\ 000$, $1 \leq K \leq 100\ 000$, $1 \leq P \leq 100\ 000$). Each of the following $K$ lines contains three integers $R$, $C$, $X$ ($1 \leq R, C \leq N$, $1 \leq X \leq 1\ 000\ 000\ 000$) which denote that initially there is a rook of power $X$ on the field $(R, C)$. Each of the following $P$ lines contains four integers $R_1$, $C_1$, $R_2$, $C_2$ ($1 \leq R_1, C_1, R_2, C_2 \leq N$) which denote that the rook has moved from field $(R_1, C_1 )$ to field $(R_2, C_2 )$. It is guaranteed that there will not be two rooks on one field at any point.

## Output

The output must consist of $P$ lines, the $k$-th line containing the total number of attacked fields after $k$ moves.

Sample Input 1 Sample Output 1
2 2 2
1 1 1
2 2 1
2 2 2 1
1 1 1 2

4
0

Sample Input 2 Sample Output 2
2 2 2
1 1 1
2 2 2
2 2 2 1
1 1 1 2

4
2

Sample Input 3 Sample Output 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

6
7
7
9