19955번 - 침략전쟁

침략 전쟁은 N × N 정사각형 모양의 격자판에서 이루어지는 온라인 게임이다. 격자판의 맨 왼쪽 위가 (1, 1)이고 맨 왼쪽 아래가 (N,1)이다.

격자판에는 여러 국가가 있으며 서로의 영토를 공격하여 전투를 펼치고 자신의 영토를 확장한다.

두 국가 간의 전투는 전투단계에 일어난다. 전투는 서로의 병사의 수만을 비교하여 승부를 가리며 병사의 수가 같다면 아무 일도 일어나지 않는다. 전투는 국가총력전을 벌이기 때문에 패배한 국가의 수도를 제외한 다른 모든 영토들은 승리한 국가에 귀속된다. 또한 전투는 병사간의 1대1 교환으로 이루어지기 때문에, 패배한 국가의 병사는 모두 사망하고 승리한 국가의 병사는 ((승리국의 전투 전 병사의 수) - (패배국의 전투 전 병사의 수))만큼 살아남는다. 수도를 잃지 않기 때문에 국가가 사라지는 일은 없다.

징집단계에 모든 국가는 보유한 영토 하나당 한 명의 병사가 늘어난다. (만약 3개의 영토를 보유한 국가가 있다면 그 국가는 3명의 병사가 늘어나게 된다.)

확장단계에는 모든 국가가 자신의 영토와 상하좌우로 인접한 영토 중 어느 국가도 소유하지 않은 영토를 귀속시키는 자동전투가 일어난다. 만약 두 개 이상의 국가가 자동전투로 같은 영토를 귀속시키려 하면 병사의 수가 가장 많은 국가가 차지한다. 병사의 수마저 같다면 번호가 더 작은 국가가 차지한다. (국가의 번호는 수도의 좌표가 (A , B)라고 했을 때 (A × N + B)이다.)

침략전쟁의 하루는 다음과 같은 순서로 진행된다.

• 첫 번째 단계는 전략단계로 각 나라들이 그날 어떠한 전략을 사용할지 구상하며 쉬어가는 단계이다.
• 두 번째 단계는 전투단계로 국가 간의 전투가 이뤄진다.
• 세 번째 단계는 징집단계로 국가별로 보유한 영토의 수만큼 병사의 수가 늘어난다.
• 네 번째 단계는 확장단계로 자동전투가 일어난다.

침략전쟁은 실시간으로 이루어지는 게임이기 때문에 두 가지 쿼리에 대한 처리를 해야 한다.

• 1 t x_a y_a x_b y_b : t일의 전투단계에 (x_a , y_a) 좌표의 영토를 소유한 국가가 (x_b , y_b)좌표의 영토를 소유한 국가를 공격한다. (두 국가가 같은 국가인 경우 아무 일도 일어나지 않으며, (x_a , y_a) 좌표의 영토를 소유한 국가와 (x_b , y_b) 좌표의 영토를 소유한 국가가 존재하는 경우만 입력으로 주어진다.)
• 2 t x_c y_c : t일의 전략단계에 (x_c , y_c) 좌표의 영토를 소유한 국가의 병사의 수를 출력한다. ((x_c , y_c) 좌표의 영토를 소유한 국가가 존재하는 경우만 입력으로 주어진다.)

초기 국가의 정보가 주어지고, 쿼리가 주어졌을 때 2번 쿼리에 따라 출력한다.

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

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

둘째 줄부터 M개의 줄에 초기 국가의 정보가 주어진다. 국가의 정보는 3개의 정수 x, y, k로 이루어져 있다. 이는 국가의 수도가 (x, y)좌표의 영토에 존재하며 병사의 수가 k명임을 의미한다.

초기 국가들은 수도 외에 영토를 갖고 있지 않는다.

다음 Q개의 줄에 위와 같은 형식의 쿼리가 주어진다.

최소 1번 이상의 2번 쿼리가 주어짐이 보장된다.

쿼리들의 순서는 날짜에 대해 오름차순임이 보장되며 같은 날짜에 여러 개의 쿼리가 들어오는 경우는 없다.

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

• 2 ≤ N ≤ 2,000
• 1 ≤ M ≤ min(N² , 1,000,000)
• 1 ≤ Q ≤ 1,000,000
• 1 ≤ x, y, x_a , y_a , x_b , y_b , x_c , y_c ≤ N
• ​1 ≤ k ≤ 1,000,000
• 1 ≤ t ≤ 1,000,000,000