뉴클레리아

오래전 뉴클레리아 사람들은 원자력 발전소를 여러 곳에 세웠다. 나라는 오랫동안 번영했지만 아주 강한 지진이 국토를 덮쳤다. 발전소가 모두 폭발했고 방사능이 전국으로 퍼졌다. 방사능이 더는 새어 나오지 않도록 조치를 마친 뒤, 환경부는 지역별 오염 정도를 조사하기 시작했다. 환경부의 질의에 답하는 프로그램을 작성하라.

방사능이 퍼지는 방식

뉴클레리아는 가로 $W$칸, 세로 $H$칸인 직사각형이다. 발전소는 각각 한 칸을 차지하고 양의 정수 두 개로 정해진다. $a$는 발전소가 있던 칸이 받는 방사능의 양이고, $b$는 발전소에서 멀어질수록 방사능이 줄어드는 속도다.

칸 $P = [x_P, y_P]$에 있던 발전소의 폭발이 칸 $C = [x_C, y_C]$에 일으키는 방사능은 $\max(0, a - b \cdot d(P, C))$이다. 여기서 $d(P, C) = \max(|x_P - x_C|, |y_P - y_C|)$이고, 체스의 킹이 두 칸 사이를 오갈 때 필요한 최소 이동 횟수와 같다.

한 칸의 총 방사능은 각 폭발이 그 칸에 일으킨 양을 모두 더한 값이다.

예를 들어 $a = 7$, $b = 3$인 발전소는 자기 칸에 방사능 7을 일으키고, 인접한 8칸에 4를, 거리가 2인 16칸에 1을 일으킨다. 발전소가 국경에 있거나 국경에서 한 칸 떨어져 있으면 폭발은 뉴클레리아 바깥 칸에도 영향을 주지만, 바깥에서 벌어지는 일은 고려하지 않는다.

질의

환경부는 직사각형 구역의 칸당 평균 방사능을 여러 번 묻는다. 질의 구역은 서로 겹치거나 완전히 같을 수도 있다.

첫 줄에 뉴클레리아의 너비 $W$와 높이 $H$가 공백을 사이에 두고 주어진다. 둘 다 양의 정수이고 $W \cdot H \le 2\,500\,000$이다.

둘째 줄에 폭발한 발전소의 수 $N$이 주어진다 ($1 \le N \le 200\,000$).

이어지는 $N$개 줄에는 각각 네 양의 정수 $x_i$, $y_i$, $a_i$, $b_i$가 주어진다 ($1 \le x_i \le W$, $1 \le y_i \le H$, $1 \le a_i, b_i \le 10^9$). 칸 $[x_i, y_i]$에 매개변수가 $a_i$, $b_i$인 발전소가 있었다는 뜻이다. 한 칸에는 발전소가 최대 하나 있다.

다음 줄에 질의의 수 $Q$가 주어진다 ($1 \le Q \le 200\,000$).

이어지는 $Q$개 줄에는 각각 네 양의 정수 $x_{1j}$, $y_{1j}$, $x_{2j}$, $y_{2j}$가 주어진다 ($1 \le x_{1j} \le x_{2j} \le W$, $1 \le y_{1j} \le y_{2j} \le H$). 왼쪽 위 칸이 $[x_{1j}, y_{1j}]$이고 오른쪽 아래 칸이 $[x_{2j}, y_{2j}]$인 직사각형을 묻는 질의다.

뉴클레리아 전체의 방사능 총합은 $2^{63}$보다 작다.

각 질의마다 그 구역의 칸당 평균 방사능을 가장 가까운 정수로 반올림해 한 줄에 하나씩 출력한다. 값이 정확히 0.5로 끝나면 올린다.

첫 번째 예제에서 두 번의 폭발이 끝난 뒤 뉴클레리아의 방사능은 다음과 같다.

7 6 3 2
4 6 5 2
1 3 3 2

질의 네 개는 이렇게 계산한다.

• $2 \times 2$ 정사각형의 방사능 총합은 14이므로 평균은 $14/4 = 3.5$이고, 반올림하면 4다.
• 뉴클레리아 전체의 총합은 44이므로 평균은 $44/12 \approx 3.67$이고, 반올림하면 4다.
• 한 칸만 묻는 질의의 평균은 그 칸의 방사능과 같다.
• 마지막 행의 평균은 $9/4 = 2.25$이므로 반올림하면 2다.