23753번 - 연결 요소와 쿼리

$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$이다.

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

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