시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 (추가 시간 없음) 1024 MB (추가 메모리 없음)153392722.314%

문제

유행은 돌고 돈다고 하지 않았던가. 스마트폰의 등장으로 많은 사람들이 종이는 이제 멸종의 길을 걷게 될 것이라고 걱정했지만, 2021년의 20대들 사이에서는 ‘다이어리 꾸미기’, 일명 ‘다꾸’가 유행이다.

우리의 청한이도 ‘다꾸’에 빠진 20대 중 한 명이다. 청한이는 다이어리를 꾸미기 위해 오늘도 지갑을 털어서 문구점에서 네모 테두리 모양 스티커를 많이 사 왔다.

청한이는 스티커를 잘라 최적의 위치에 붙이고 #다꾸 #다이어리꾸미기 #다꾸스타그램 #스꾸 #스티커 #스티커꾸미기 해시를 달아 SNS에 자랑할 생각에 신이 나 있다. 하지만 스티커를 어떻게 잘라 붙여야 잘 붙였다고 소문이 날까 고민이었던 나머지, 전공을 살려 다꾸러들의 미적 감각을 빅데이터로 분석하여 가장 높은 좋아요 수를 이끌어낼 만한 스티커 위치를 계산해 주는 인공지능을 만들기로 했다.

다이어리 속지는 높이 $H$, 너비 $W$의 격자 모양이다. 맨 왼쪽 위 칸을 $\left(1, 1\right)$, 맨 오른쪽 아래 칸을 $\left(H, W\right)$로 나타낼 수 있다. 청한이는 빅데이터를 활용해 어떤 칸에 스티커가 붙으면 얼마나 ‘예쁜지’를 각 칸마다 계산해 두었다. 이 값은 $-10^9$ 이상 $10^9$ 이하의 정수이다.

네모 테두리 모양 스티커의 테두리 두께는 한 칸이다. 즉, $(x_1, y_1)$과 $(x_2, y_2)$를 대각 꼭지점으로 한 직사각형의 테두리는 $(x_1, y_1)$과 $(x_2, y_2)$를 대각 꼭지점으로 한 직사각형에서 $(x_1+1, y_1+1)$과 $(x_2-1, y_2-1)$를 대각 꼭지점으로 한 직사각형 부분을 제외했다는 의미이다. ($x_1 + 2 \leq x_2$, $y_1 + 2 \leq y_2$) 여러 가지 크기의 스티커가 준비되어 있지만 청한이는 어떤 직사각형 영역을 정해 그 직사각형 영역에 꼭 맞는 크기의 스티커를 고를 것이다.

스티커의 ‘예쁨’은 스티커가 다이어리에 붙었을 때 가려진 칸들의 ‘예쁨’의 합이다. 고른 스티커를 영역의 테두리에 맞춰 붙일 때 제일 예쁘게 붙을 수 있도록 적절히 잘라 한 조각만 붙일 것이다. 물론 스티커를 자르지 않고 테두리 모양 전체를 붙일 수도 있다. 스티커가 새로 붙어도 각 칸의 ‘예쁨’은 바뀌지 않는다.

또한 청한이는 올망졸망한 손글씨로 오늘 있었던 일을 쓰려고 한다. 이 경우 청한이가 정한 칸의 ‘예쁨’이 바뀐다.

청한이는 이미 스티커가 붙은 위치 위에 스티커를 겹쳐 붙일 수도 있고, 손글씨가 적혀 있는 자리에 스티커를 덮어 붙일 수도 있다. 청한이를 도와 최적의 스티커 위치를 정해 주자.

입력

다음과 같이 입력이 주어진다.

$H$ $W$ $T$
$\begin{matrix} A_{1,1} & A_{1,2} & \cdots & A_{1,W} \\ A_{2,1} & A_{2,2} & \cdots & A_{2,W} \\ \vdots & \vdots & \ddots & \vdots \\ A_{H,1} & A_{H,2} & \cdots & A_{H,W} \end{matrix}$
$op_1$
$\vdots$
$op_T$
  • $H$와 $W$는 다이어리 내지의 크기를 나타내는 정수이다. ($3 \leq H$, $3 \leq W$, $9 \leq HW \leq 10^6$)
  • $T$는 청한이가 다이어리 꾸미기를 하는 횟수이다. ($1 \leq T \leq 100\,000$)
  • $A_{ij}$는 $\left(i,j\right)$의 최초 ‘예쁨’이다. ($-10^9 \leq A_{ij} \leq 10^9$)
  • $op_i$는 청한이가 다이어리를 어떻게 꾸밀지를 설명한다.
    • 스티커를 붙이려는 경우, 다음과 같이 주어진다. 이는 칸 $\left(x_1, y_1\right)$ 과 $\left(x_2, y_2\right)$ 를 대각 꼭지점으로 하는 네모 테두리 모양 지점에 스티커를 붙일 예정임을 의미한다.
      $1$ $x_1$ $y_1$ $x_2$ $y_2$
      • $1 \leq x_1 < x_2 \leq H$, $1 \leq y_1 < y_2 \leq W$
      • $x_1 + 2 \leq x_2$, $y_1 + 2 \leq y_2$
    • 손글씨를 쓰려는 경우, 다음과 같이 주어진다. 이는 칸 $\left(x,y\right)$의 ‘예쁨’ 값을 $p$ 로 변경한다는 의미이다.
      $2$ $x$ $y$ $p$
      • $1 \leq x \leq H$, $1 \leq y \leq W$, $-10^9 \leq p \leq 10^9$

출력

스티커를 붙일 때마다, 청한이가 스티커를 최대한으로 예쁘게 붙였을 때의 예쁨을 한 줄에 하나씩 출력한다.

예제 입력 1

4 4 3
3 2 -6 4
1 9 8 2
6 4 8 -7
-2 0 4 8
1 1 1 4 4
2 2 1 -9
1 1 1 4 4

예제 출력 1

22
16

예제 입력 2

4 8 2
0 0 2 0 0 -1 -1 -1
0 1 1 1 0 -1 9 -1
0 1 1 1 0 -1 -1 -1
0 2 -9 2 0 1 1 1
1 1 1 4 5
1 1 6 3 8

예제 출력 2

6
-1