발전량 증감

문제

2 3
1 2 4
8 16 32
3
1 1 2 3
1 2 1 2
1 3 2 3

63
2
36

2 2
1349 970
2754 -519
2
1 2 1 2
2 2 2 2

970
-519

1 1
6042
1
1 1 1 1

6042

입력 조건

• 가장 먼저 첫째 줄에 격자의 행의 수 N과 열의 수 M이 공백으로 구분되어 주어진다. N과 M은 각각 1 이상 300 이하의 자연수다.

• 이어서 N개의 줄에 걸쳐 격자에 적힌 값이 주어진다. 각 줄에는 M개의 수가 공백으로 구분되어 주어지며, 각 값은 절댓값이 10,000 이하인 정수다.

• 이어서 다음 줄에 조회의 횟수 K가 주어진다. K는 1 이상 10,000 이하의 자연수다.

• 이어서 K개의 줄에 걸쳐 각 조회의 정보가 주어진다. 각 줄에는 네 개의 수 i, j, x, y가 공백으로 구분되어 주어진다. i는 1 이상 N 이하의 자연수이고 x는 i 이상 N 이하의 자연수다. j는 1 이상 M 이하의 자연수이고 y는 j 이상 M 이하의 자연수다.

• 입력 전체의 크기는 최대 약 0.6MB다. 줄의 수가 최대 10,302개이므로, 입력 전체를 한 번에 읽어서 줄 단위로 나누는 방식으로 처리해야 한다.

출력 조건

• K번의 조회 결과를 한 줄에 하나씩 차례대로 출력한다. 마지막 결과 뒤에는 줄바꿈 하나만 붙으며, 빈 줄을 더 붙이지 않는다.

요구사항

• 조회는 항상 i가 x보다 작거나 같고, j가 y보다 작거나 같은 형태로 주어집니다
• 왼쪽 위 모퉁이와 오른쪽 아래 모퉁이가 같은 칸이면 그 칸의 값 하나만 더합니다
• 격자에 적힌 값은 음수일 수 있고, 구역의 합도 음수일 수 있습니다
• 조회가 최대 1만 번이므로 조회마다 직사각형을 다시 더하면 시간이 모자랍니다
• 출력의 끝에 빈 줄을 더 붙이지 않습니다
• 표준 입력으로 읽고 표준 출력으로 내보내는 프로그램을 짜야 합니다
• 쓸 수 있는 말은 파이썬, 자바스크립트입니다
• 메모리 제한은 256MB입니다. 브라우저에서는 재지 않고 적기만 합니다
• 시간 제한은 출제자의 정답 코드를 같은 런타임에서 재서 정합니다
• 이 문제는 프롬프트가 아니라 코드를 냅니다. 그 코드는 이 기기의 브라우저에서 돌고, 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다. 실행 시간은 각자 기기가 적어 보내는 값이라, 코드와 기기 정보를 순위표에 같이 내걸어 둡니다.
• 출력이 글자 하나까지 기대값과 같아야 합니다. 줄 안의 빈칸은 다른 글자와 똑같이 봅니다.
• 케이스는 15개이고, 그 가운데 3개는 입력과 기대 출력을 함께 보여 줍니다. 나머지는 제출할 때만 쓰이고 화면에는 보여 주지 않습니다.
• 케이스 15개를 전부 통과해야 해결입니다.

예시

공개 케이스 3개입니다. 채점에는 숨은 케이스가 함께 쓰입니다. 케이스 15개를 전부 통과해야 해결입니다.

1 1
6042
1
1 1 1 1

6042

2 2
1349 970
2754 -519
2
1 2 1 2
2 2 2 2

970
-519

2 3
1 2 4
8 16 32
3
1 1 2 3
1 2 1 2
1 3 2 3

63
2
36