문제
정현이는 체스와 프로그래밍을 매우 좋아한다. 하지만 전통적인 체스에 싫증이 나서 새로운 체스게임을 고안했다.
정현이의 체스 게임은 룩(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번째 이동 후 점유 할 수 있는 필드의 개수를 의미한다.
예제1
입력
222
111
221
2221
1112
출력
4
0
예제2
입력
222
111
222
2221
1112
출력
4
2
예제3
입력
334
111
222
233
2333
3331
1112
3132
출력
6
7
7
9
출처
COCI 2015/2016 contest1 4