시간 제한 메모리 제한 제출 횟수 정답 횟수 (비율) 정답자 수
2.0 초 64 MB 2 2 (100%) 2
문제
시간 제한 2초, 메모리 제한 64MB Mirko는 체스와 프로그래밍을 좋아한다. 하지만 평범한 체스가 질리기 시작하여 그는 룩(체스 말의 종류)를 가지고 놀기 시작했다. 그는 $N$개의 행과 $N$개의 열을 가진 체스판 위에 $K$개의 룩을 올려두었다. Mirko의 게임은 아래와 같은 규칙을 가진다. 1. 각 룩의 힘은 정수로 정의된다. 2. 룩은 자기자신을 제외하고 같은 행, 열을 가진 자리들을 모두 볼 수 있다. 3. 체스판 위의 어떤 자리에서 그 자리를 볼 수 있는 룩들의 힘의 XOR값이 0보다 크다면 그 자리는 공격당했다고 한다. 룩이 있는 자리도 공격당하거나 당하지 않을 수도 있다. Mirko는 처음에 룩들을 적당하게 배치해 두었고 이후에 그들을 $P$번 옮기게 될 것이다. 각 움직임 후 몇 개의 자리가 공격당하게 되는지 구하여라. 룩은 판 전체의 모든 빈자리로 이동할 수 있다(움직임이 행과 열로만 제한되는 것이 아니다.)
입력
첫째 줄에 $N, K, P(1 ≤ N ≤ 1,000,000,000, 1 ≤ K ≤ 100,000, 1 ≤ P ≤ 100,000)$가 주어진다. 다음 $K$개의 줄에는 3개의 정수 $R, C, X(1 ≤ R, C ≤ N, 1 ≤ X ≤ 1,000,000,000)$가 주어지는데 이는 힘 $X$를 가진 룩이 처음에 판의 $(R, C)$에 위치한다는것을 의미한다. 다음 $P$개의 줄에는 4개의 정수 $R_1, C_1, R_2, C_2(1 ≤ R_1, C_1, R_2, C_2 ≤ N)$가 주어지고 이는 룩이 $(R_1, C_1)$에서 $(R_2, C_2)$로 이동했음을 의미한다. 두 개의 룩이 같은 자리에 존재하는 경우는 어떤 시점에도 존재하지 않는다.
출력
$P$개의 줄을 출력하는데 각 $k$번째 줄에는 $k$번 움직인 후 공격당하는 자리의 개수를 출력한다.
힌트
#### 점수 25%의 경우에 $N$과 $K$는 100을 넘지 않는다. #### 예제 입력 1 ``` 2 2 2 1 1 1 2 2 1 2 2 2 1 1 1 1 2 ``` #### 예제 출력 1 ``` 4 0 ``` #### 예제 입력 2 ``` 2 2 2 1 1 1 2 2 2 2 2 2 1 1 1 1 2 ``` #### 예제 출력 2 ``` 4 2 ``` #### 예제 입력 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 ``` #### 예제 출력 3 ``` 6 7 7 9 ``` #### 예제 설명 1 첫 번째 움직임 후에 판 위의 모든 자리는 공격당하게 된다. 예를 들면 $(1, 1)$은 하나의 룩이 보고 있고 XOR값은 1이 된다. 두 번째 움직임 후에는 모든 자리가 공격받지 않게 된다. 예를 들어 $(1, 1)$은 두 룩이 모두 보고 있는 자리이므로 총 XOR값이 0이 된다.