25826번 - 2차원 배열 다중 업데이트 단일 합

크기가 n x n인 정수형 2차원 배열 A가 주어진다. 배열 A의 원소는 A[0][0], A[0][1], …, A[n - 1][n - 1]이다. 배열 A의 모든 원소의 초깃값은 입력으로 주어진다. 배열 A에 대한 m개의 질의가 저장된 배열 B가 주어진다. 배열 B에 저장된 m개의 질의는 아래 두 가지 유형으로 구분된다. 첫 번째가 유형 1을 나타내고 두 번째가 유형 2를 나타낸다.

• 1 i₁ j₁ i₂ j₂ k : 행 번호 i가 i₁ ≤ i ≤ i₂이고, 열 번호 j가 j₁ ≤ j ≤ j₂인 A[i][j]에 k를 더한다.
• 2 i₁ j₁ i₂ j₂ : 행 번호 i가 i₁ ≤ i ≤ i₂이고, 열 번호 j가 j₁ ≤ j ≤ j₂인 A[i][j]의 합을 출력한다.

배열 B에 저장된 첫 번째 질의부터 m번째 질의까지 순서대로 처리하면서 유형 2에 대한 결과를 출력하자. 단, 배열 B에는 유형 2의 질의가 마지막에 1개만 저장되어 있다.

첫 번째 줄에 n과 m이 공백을 사이에 두고 순서대로 주어진다.

두 번째 줄부터 n개의 줄에 배열 A의 원소가 주어진다. i번째 줄의 j번째 수는 배열 A의 (i - 1)번째 행 (j - 1)번째 열의 원소 A[i - 1][j - 1]을 나타낸다.

다음 줄부터 m개의 줄에 걸쳐서 배열 B에 저장된 m개의 질의가 순서대로 주어진다. 한 줄에 하나의 질의를 나타내는 수가 공백을 사이에 두고 순서대로 주어진다.

첫 번째 줄에 유형 2의 질의 결과를 출력한다.

• 1 ≤ n ≤ 1,000, 1 ≤ m ≤ 300,000
• 1 ≤ A[i][j] ≤ 1,000,000 (0 ≤ i, j ≤ n - 1)
• 배열 B에 저장된 질의는 유형 1과 유형 2만 존재한다.
• 배열 B에는 유형 2의 질의가 마지막에 1개만 저장되어 있다.
• 0 ≤ i₁ ≤ i₂ ≤ n - 1
• 0 ≤ j₁ ≤ j₂ ≤ n - 1
• 1 ≤ k ≤ 10,000