웜뱃

브리즈번 시가 돌연변이로 거대해진 웜뱃(호주에 사는, 너구리를 닮은 동물)에게 점령당했습니다. 여러분의 임무는 사람들을 남쪽으로 안전하게 구조하는 것입니다.

브리즈번의 도로는 커다란 격자 형태입니다. 동서 방향(가로)으로 놓인 수평 도로가 $R$개 있고 북쪽에서 남쪽으로 $0, 1, \dots, R-1$번이 매겨져 있습니다. 남북 방향(세로)으로 놓인 수직 도로가 $C$개 있고 서쪽에서 동쪽으로 $0, 1, \dots, 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$입니다.
• 변경 이벤트가 두 번 일어납니다. 수직 도로 $0$번의 가장 위쪽 세그먼트의 웜뱃 수가 $5$로 바뀌고, 수평 도로 $1$번의 가운데 세그먼트의 웜뱃 수가 $6$으로 바뀝니다. 아래 그림에서 동그라미 친 숫자를 확인하세요.

세 번째 사람이 다시 교차로 $A = (0, 2)$에 도착해 교차로 $B = (2, 1)$로 도망치려 합니다. 이번에는 만나는 웜뱃 마릿수의 최솟값이 $5$입니다.

도로의 구조와 각 세그먼트의 웜뱃 마릿수, 그리고 이벤트가 발생 순서대로 주어질 때 이를 처리하는 프로그램을 작성하세요.

첫째 줄에 수평 도로의 수 $R$과 수직 도로의 수 $C$가 공백으로 구분되어 주어집니다. ($2 \le R \le 5000$, $1 \le C \le 200$)

이어지는 $R$개의 줄에는 수평 세그먼트 정보가 주어집니다. $i$번째 줄($0 \le i \le R-1$)에는 $C-1$개의 정수 H[i][0]부터 H[i][C-2]까지가 주어지며, H[i][j]는 교차로 $(i, j)$와 $(i, j+1)$ 사이 수평 세그먼트의 웜뱃 마릿수입니다.

그다음 $R-1$개의 줄에는 수직 세그먼트 정보가 주어집니다. $i$번째 줄($0 \le i \le R-2$)에는 $C$개의 정수 V[i][0]부터 V[i][C-1]까지가 주어지며, V[i][j]는 교차로 $(i, j)$와 $(i+1, j)$ 사이 수직 세그먼트의 웜뱃 마릿수입니다.

그다음 줄에 이벤트의 수 $E$가 주어집니다.

이어지는 $E$개의 줄에는 이벤트가 발생 순서대로 한 줄에 하나씩 주어집니다. 각 이벤트는 다음 세 형식 중 하나입니다.

• 1 P Q W: 교차로 $(P, Q)$와 $(P, Q+1)$ 사이 수평 세그먼트의 웜뱃 마릿수를 $W$로 바꿉니다. ($0 \le P \le R-1$, $0 \le Q \le C-2$, $0 \le W \le 1000$)
• 2 P Q W: 교차로 $(P, Q)$와 $(P+1, Q)$ 사이 수직 세그먼트의 웜뱃 마릿수를 $W$로 바꿉니다. ($0 \le P \le R-2$, $0 \le Q \le C-1$, $0 \le W \le 1000$)
• 3 V1 V2: 교차로 $(0, V1)$에서 $(R-1, V2)$로 이동할 때 만나는 웜뱃 마릿수의 최솟값을 묻습니다. ($0 \le V1 \le C-1$, $0 \le V2 \le C-1$)

1번과 2번 이벤트는 합쳐서 최대 $500$번, 3번 이벤트는 최대 $200000$번 발생합니다. 어느 시점에서든 한 세그먼트의 웜뱃 마릿수는 항상 $1000$ 이하입니다.

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