정현이는 체스와 프로그래밍을 매우 좋아한다. 하지만 전통적인 체스에 싫증이 나서 새로운 체스게임을 고안했다. 

정현이의 체스 게임은 룩(Rook)말들을 이용하는 것으로 아래와 같은 규칙을 갖는다.

 

1. N * N 체스 판에 K개의 룩(Rook)을 놓는다.

2. 각각의 룩은 정수단위의 힘을 갖고 있다.

3. x행 y열 필드(체스 판의 모든 셀들을 필드라고 부른다.) 에 어떤 룩(Rook)이 위치해 있을 경우 

   그 룩은 x행 전체와 y열 전체를 볼 수 있다. 단, 자신이 위치한 필드를 볼 수는 없다.

4. 어떤 필드가 그 필드를 볼 수 있는 모든 룩(Rook)들의 힘값들을 모두 XOR연산 값이 0초과이면 점유되었다고 말한다.

 

< XOR 연산>

XOR 연산은 비트연산자 중 하나로서 각각을 이진수로 바꾼 후 같은 자리의 비트가 같으면 

그 자리의 XOR연산 결과 값은 0이 되고 다르면 1이 된다.

정수 10과 3을 XOR연산한 결과를 보자. 먼저 각각을 이진수로 바꾸어 4자리로 나타내면

10 => 1010

3 => 0011 이 되고 결과 값은

1001 이 되어 10진 정수로 나타내면 9가 된다.

 

초기에 정현이는 룩(Rook)들을 체스 판에 배치한다. 그리고 P번 이동시킨다. 

각각의 이동 후에 점유되는 필드는 얼마나 될까? 모든 룩(Rook)은 비어있는 임의의 필드로 이동될 수 있다.

 

첫 행에 체스 판의 크기 N, 룩의 개수 K, 이동 횟수 P가 공백으로 구분되어 주어진다.(1 ≤ N ≤ 1,000,000,000, 1 ≤ K ≤ 100,000, 1 ≤ P ≤ 100,000) 다음 K개의 행에 R, C, X가 입력된다. R, C는 룩이 놓이는 행과 열 번호이고 X는 룩(Rook)의 힘을 나타낸다. (1 ≤ R, C ≤ N, 1 ≤ X ≤ 1,000,000,000) 다음 P개의 행에 R1, C1, R2, C2(1 ≤ R1, C1, R2, C2 ≤ N)가 입력된다. R1, C1 필드에 있는 룩을 R2, C2필드로 이동시키라는 의미이다. 입력데이터는 어떤 두 개 이상의 룩(Rook)도 같은 필드에 놓이지 않는 것을 보증한다.

출력은 P개의 행으로 이루어진다. Pi번 행의 값은 Pi번째 이동 후 점유 할 수 있는 필드의 개수를 의미한다.

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