Informatica Online Judge

  Hard Game (Hard) [1368 / 0558]

Time Limit(Test case) : 2000 (ms)
Number of users who solved : 2   Total Tried : 6


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[koistudy.net (32nd 유재민)]

Background

카미조 토우마는 불행한 사람이다.

그는 어떤 게임을 하고 있는데 이 게임은 총알을 피하는 게임이다.
각 라운드 마다 출발지와 도착지가 정해지는데 플레이어는 자신의 캐릭터를 출발지에서 도착지로 이동시키고 이동시키는 동안 날아오는 총알을 피해야 한다.
플레이어의 캐릭터는 2차원 평면 상에 놓여있는데 세로 N칸, 가로 M칸인 직사각형 모양이다.

모든 칸에는 터렛이 있는데 (i,j) 위치에(가로로 i번째, 세로로 j번째 위치이다) 있는 터렛은 x=i, y=j 직선위를 감시하며 플레이어의 캐릭터가 이 직선위를 통과하면 총알을 발사한다. 즉, 터렛은 자신의 위치와 같은 x좌표, y좌표를 감시하는 것이다.

모든 칸에 터렛이 있기 때문에 도착지와 출발지에서도 총알을 맞을 수 있을 것이라 생각되지만 출발지나 도착지와 같은 x좌표, 같은 y좌표 위에 있는 터렛들의 기능이 일시적으로 동결되기 때문에 도착지와 출발지에서는 총알을 맞지 않는다.

처음에 캐릭터는 (1,1)에서 출발하며 이번 라운드에서 도착지였던 곳이 다음 라운드의 출발지가 된다.

카미조 토우마는 불행한 사람이기 때문에 총알을 하나도 피할 수 없다. 즉, 터렛에서 발사된 총알을 모두 맞는다.
각각의 터렛에는 공격력이 있는데 캐릭터가 총알을 맞으면 그 총알을 쏜 터렛의 공격력만큼 피해를 받는다.

게임은 시간이 지날수록 점점 어려워지는데 그 이유는 중간중간에 터렛들의 공격력이 증가하기 때문이다. 공격력이 증가하는 터렛들의 영역은 직사각형이며 그 직사각형에 속한 터렛들은 같은 크기만큼 공격력이 증가한다.

불행한 토우마가 각 라운드마다 받는 총 피해량을 구해보자.

Input

첫줄에 맵의 세로와 가로인 N,M이 주어진다.
2번째 줄부터 N+1번째 줄까지 터렛들의 초기 공격력이 N*M개 주어진다.
N+2번째 줄에 쿼리의 개수 Q가 주어진다.
그 다음 줄부터 쿼리가 Q개 들어오는데 쿼리의 종류는 다음과 같다.

1 x y : (x,y)가 도착지이다. 즉, 현재 라운드에서 캐릭터를 (x,y)로 이동시켜야 함을 의미한다. 처음에 출발지는 (1,1)이며 그 다음 부터는 이전 라운드의 도착지가 출발지이다.
이 쿼리를 받으면 이 라운드에서 받는 피해량을 출력한다.

2 p q x y c : (p,q)에서 (x,y)까지 직사각형의 영역(p≤i≤x, q≤j≤y인 (i,j)들의 집합) 안에 있는 터렛의 공격력을 c만큼 증가시킨다. (p≤x, q≤y임이 보장된다)


입력범위 : N<1000, M<1000, Q<10000

Output

각 라운드마다 토우마가 받는 피해량을 출력한다.

IO Example

Input
5 5
1 0 1 3 1
2 1 1 3 2
4 1 1 2 1
3 2 1 4 1
2 1 3 2 2
6
1 2 3
2 1 1 5 5 3
1 3 2
1 2 4
2 2 1 3 4 4
1 1 1


Output
6
0
16
36

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]