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

문제

$K \times N$ 격자 그래프 $A$가 주어진다. 격자 그래프는 노드가 직사각형 모양으로 배치되어 있는 그래프이며, 각 노드는 위, 아래, 왼쪽, 그리고 오른쪽 노드와 연결되어 있다.

위에서 $x$번째 줄 왼쪽에서 $y$번째 칸의 노드를 $A_{xy}$로 나타내자. 이 때, 다음 쿼리를 수행하는 프로그램을 작성하시오.

  • 1 x1 y1 x2 y2: $x_1 \le x \le x_2$, $y_1 \le y \le y_2$인 $A_{xy}$만으로 이루어진 크기 $1$ 이상의 연결 요소 중, 구성 노드의 값의 합이 가장 큰 연결 요소를 찾아 그 합을 출력한다.
  • 2 x y v: $A_{xy}$의 값을 $v$로 설정한다.

입력

첫 번째 줄에 격자 그래프의 크기를 나타내는 정수 $K$, $N$이 주어진다. ($K \in \left\{1,2,3\right\}$, $1 \le N \le 100\,000$)

두 번째 줄부터 $K$개의 줄에 걸쳐 격자 그래프의 노드의 값들이 주어진다. ($-10^9 \le A_{ij} \le 10^9$)

다음 줄에는 쿼리의 개수 $Q$가 주어진다. ($1 \le Q \le 100\,000$)

다음 줄부터 $Q$개의 쿼리가 문제에서 언급한 형식으로 한 줄에 하나씩 주어진다.

  • $1$번 쿼리에서 $1 \le x_1 \le x_2 \le K$, $1 \le y_1 \le y_2 \le N$이다.
  • $2$번 쿼리에서 $1 \le x \le K$, $1 \le y \le N$, $-10^9 \le v \le 10^9$이다.

입력으로 들어오는 모든 수는 정수다.

출력

각각의 쿼리마다 정답을 한 줄에 하나씩 출력한다.

예제 입력 1

3 8
-1 5 6 3 -1 7 -6 9
6 8 -9 2 -4 5 1 8
3 4 1 5 -7 -3 2 7
4
1 1 2 3 7
2 1 5 -100
1 1 2 3 7
1 2 2 2 4

예제 출력 1

48
45
8

출처

University > 서강대학교 > 2021 Sogang Programming Contest (Champion) H번