시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
20 초 256 MB 21 6 6 30.000%

문제

브리즈번 시는 돌연변이로 거대해진 웜뱃(호주에 사는 너구리 비슷한 동물)에 장악당했다. 당신의 임무는 사람들을 구조하는 것이다.

브리즈번 시의 도로는 커다란 격자 모양으로 되어 있다. 동서 방향으로 놓인 수평 도로는 R 개가 있고, 북쪽에서 남쪽 방향으로 차례로 번호가 0, …, (R - 1) 로 매겨져 있다. 또한, 남북 방향으로 놓인 수직 도로는 C 개가 있고, 서쪽에서 동쪽 방향으로 차례로 번호가 0, …, (C - 1) 로 매겨져 있다. 다음 그림은 이렇게 번호가 매겨진 도로의 예이다.

웜뱃은 북쪽에서부터 쳐들어오고 있고, 사람들은 남쪽으로 도망친다. 사람들은 가로 방향으로는 어느 쪽이든 움직일 수 있지만, 세로 방향으로는 안전한 방향인 남쪽으로만 움직일 수 있다.

수평 도로 P 와 수직 도로 Q 의 교차로는 (P, Q) 로 표현한다. 두 교차로 사이 세그먼트에는 웜뱃들이 있을 수 있고, 몇 마리의 웜뱃이 있는지는 시간이 흐르면서 변할 수 있다. 여러분의 임무는 북쪽(수평 도로 0 번)의 주어진 교차로에 도착한 사람을 남쪽(수평 도로 R - 1 번)의 주어진 교차로로 가는 길을 알려주는 것인데, 이 경로를 지날 때 가능한 한 적은 수의 웜뱃을 만나야 한다.

먼저, 격자의 크기와 각 도로 세그먼트에 웜뱃이 몇 마리가 있는지가 주어진다. 다음에는 E 개의 이벤트가 차례로 주어지는데, 각 이벤트는 아래 두 가지 중 하나의 형태이다.

change : 어떤 도로 세그먼트에 있는 웜뱃의 마릿수가 바뀐다.
escape : 사람 한 명이 수평 도로 0 번의 주어진 교차로로 도착하고, 이 사람을 가장 적은 수의 웜뱃을 만나면서 수평 도로 R - 1 의 주어진 교차로로 보내는 경로를 구해야 한다.

위 그림은 수평 도로가 R = 3 개, 수직 도로가 C = 4 개, 그리고 각 도로 세그먼트에 웜뱃이 몇 마리가 있는지 주어진 지도의 처음 상황이다. 다음 순서대로 이벤트가 발생한다고 하자.

한 사람이 교차로 A = (0, 2) 에 도착해서 교차로 B = (2, 1) 로 도망치고 싶어한다. 이 때 만나는 웜뱃 마릿수의 최소값은 2 인데, 점선을 따라가면 이를 확인할 수 있다.

또 한 사람이 교차로 X = (0, 3) 에 도착해서 교차로 Y = (2, 3) 로 도망치고 싶어한다. 이 때 만나는 웜뱃 마릿수의 최소값은 7 인데, 또 점선을 따라가면 이를 확인할 수 있다.

change 이벤트가 두 번 발생한다. 수직 도로 0 의 가장 위 세그먼트에 있는 웜뱃의 수가 5 마리로 바뀌고, 수평 도로 1 의 가운데 세그먼트에 있는 웜뱃의 수가 6 마리로 바뀐다. 아래 그림의 동그라미를 친 숫자를 확인해보자.

세 번째 사람이 교차로 A = (0, 2) 에 도착해서 교차로 B = (2, 1) 로 도망치고 싶어한다. 이번에는 만나게 되는 웜뱃의 최소 숫자가 5 마리이고, 다시 점선을 따라가면 이를 확인할 수 있다.

도로의 모양과 각 도로 위의 웜뱃의 수가 주어진다. 그 다음 이벤트가 발생한 순서대로 주어졌을 때, 이를 처리하는 프로그램을 작성하시오.

입력

첫째 줄에 수평 도로의 수 R과 수직 도로의 수 C가 주어진다.  (2 ≤ R ≤ 5,000, 1 ≤ C ≤ 200)

둘째 줄부터 R+1번째 줄에는 H[i][j]가 주어진다. 각 줄에 주어지는 숫자는 총 C-1개이며, H[i][0]부터 H[i][C-2]까지다. H[i][j]는 교차로 (i,j)와 (i,j+1) 사이의 수평 도로 세그먼트 상의 웜뱃의 마릿수를 나타낸다.

R+2번째 줄부터 2R번째 줄에는 V[i][j]가 주어진다. 각 줄에 주어니는 숫자는 총 C개이며, V[i][0]부터 V[i][C-1]까지다. V[i][j]는 교차로 (i,j)와 (i+1,j) 사이의 수직 도로 세그먼트 상의 웜뱃의 마릿수를 나타낸다.

다음 줄에는 발생하는 이벤트의 수 E가 주어진다.

다음 E개 줄에는 이벤트가 발생하는 순서대로 한 줄마다 이벤트가 하나씩 주어진다.

교차로 (P,Q)와 (P,Q+1)사이의 수평 도로 세그먼트 위의 웜뱃의 마릿수를 바꾸는 이벤트는 "1 P Q W" 형식으로 주어진다. (0 ≤ P ≤ R-1, 0 ≤ Q ≤ C-2, 0 ≤ W ≤ 1,000)

교차로 (P,Q)와 (P+1,Q)사이의 수직 도로 세그먼트 위의 웜뱃의 마릿수를 바꾸는 이벤트는 "2 P Q W" 형식으로 주어진다. (0 ≤ P ≤ R-2, 0 ≤ Q ≤ C-1, 0 ≤ W ≤ 1,000)

교차로 (0,V1)에서 (R-1,V2)로 지나갈 때 만나는 웜뱃 마릿수의 최소값을 구하는 이벤트는 "3 V1 V2" 형식으로 주어진다. (0 ≤ V1 ≤ C-1, 0 ≤ V2 ≤ C-1)

1번과 2번 이벤트는 합쳐서 최대 500번 발생하며, 3번은 최대 200,000번 발생한다. 한 세그먼트에 있는 웜뱃의 마릿수는 항상 1,000 이하이다.

출력

3번 이벤트가 발생할 때 마다, 교차로 (0,V1)에서 (R-1,V2)로 지나갈 때 만나는 웜뱃 마릿수의 최소값을 한 줄에 하나씩 순서대로 출력한다.

예제 입력

3 4
0 2 5
7 1 1
0 4 0
0 0 0 2
0 3 4 7
5
3 2 1
3 3 3
2 0 0 5
1 1 1 6
3 2 1

예제 출력

2
7
5

힌트