침략 전쟁

침략 전쟁은 $N \times N$ 크기의 정사각형 격자판에서 진행되는 온라인 게임이다. 격자판의 왼쪽 위 칸은 (1, 1)이고 왼쪽 아래 칸은 (N, 1)이다.

격자판에는 여러 국가가 있다. 국가들은 서로의 영토를 공격해 전투를 벌이고 자신의 영토를 넓힌다.

두 국가의 전투는 전투단계에 일어난다. 전투는 병사 수만 비교해 승패를 가리며, 병사 수가 같으면 아무 일도 일어나지 않는다. 국가 총력전이므로 패배한 국가의 수도를 제외한 모든 영토는 승리한 국가에 귀속된다. 전투는 병사끼리 일대일로 맞바꾸는 방식이다. 패배한 국가의 병사는 모두 죽고, 승리한 국가의 병사는 (전투 전 승리국의 병사 수) - (전투 전 패배국의 병사 수)만큼 살아남는다. 패배한 국가는 수도를 지키므로 국가가 사라지는 일은 없다.

징집단계에는 모든 국가가 보유한 영토 하나당 병사 한 명을 얻는다. 영토를 3개 가진 국가는 병사가 3명 늘어난다.

확장단계에는 자동 전투가 일어난다. 각 국가는 자신의 영토와 상하좌우로 인접한 영토 중 어느 국가도 소유하지 않은 영토를 차지한다. 두 국가 이상이 같은 영토를 차지하려 하면 병사가 가장 많은 국가가 차지한다. 병사 수도 같으면 번호가 작은 국가가 차지한다. 국가의 번호는 수도 좌표가 (A, B)일 때 $A \times N + B$이다.

하루는 다음 순서로 진행된다. 첫 번째는 전략단계로, 각 국가가 그날의 전략을 구상하며 쉬는 단계다. 두 번째는 전투단계, 세 번째는 징집단계, 네 번째는 확장단계다.

게임은 0일의 징집단계부터 시작한다.

첫 줄에 격자판의 크기 N, 초기 국가의 수 M, 쿼리의 수 Q가 주어진다.

다음 M개의 줄에는 정수 x, y, k가 주어진다. 이는 수도가 (x, y) 좌표의 영토에 있고 병사가 k명인 국가를 뜻한다. 초기 국가는 수도 외에 영토를 갖고 있지 않다.

다음 Q개의 줄에는 아래 두 형식 중 하나의 쿼리가 주어진다.

1 t xa ya xb yb 쿼리는 t일의 전투단계에 (xa, ya) 좌표의 영토를 소유한 국가가 (xb, yb) 좌표의 영토를 소유한 국가를 공격한다는 뜻이다. 두 영토가 같은 국가의 소유라면 아무 일도 일어나지 않는다. 두 좌표의 영토를 소유한 국가는 항상 존재한다.

2 t xc yc 쿼리는 t일의 전략단계에 (xc, yc) 좌표의 영토를 소유한 국가의 병사 수를 출력하라는 뜻이다. 해당 좌표의 영토를 소유한 국가는 항상 존재한다.

2번 쿼리가 주어질 때마다 해당 국가의 병사 수를 한 줄에 하나씩 출력한다.

$2 \le N \le 2{,}000$

$1 \le M \le \min(N^2, 1{,}000{,}000)$

$1 \le Q \le 1{,}000{,}000$

$1 \le x, y, x_a, y_a, x_b, y_b, x_c, y_c \le N$

$1 \le k \le 1{,}000{,}000$

$1 \le t \le 1{,}000{,}000{,}000$