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:
- Each rook’s power is determined by an integer.
- A rook sees all the fields that are in his row or column except its own field.
- 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.

-----Examples-----
Sample Input 1:
2 2 2
1 1 1
2 2 1
2 2 2 1
1 1 1 2
Sample Output 1:
4
0

Sample Input 2:
2 2 2
1 1 1
2 2 2
2 2 2 1
1 1 1 2
Sample Output 2:
4
2

见题面

见题面