이제 다시 시작이다

논산에 도착한 욱제는 DJ욱제였던 시절의 기억들을 회상하고 있다.

욱제는 훈련소에서 새로운 시작을 하기 전에 마지막으로 자신의 예술을 알리기 위한 광역디제잉을 준비했다.

1. 논산은 2차원 격자로 표현되며, 두 점 (x1, y1), (x2, y2)의 거리는 | x1 - x2 | + | y1 - y2 |이다.
2. 훈련소는 축에 평행한 직사각형으로, 왼쪽 아래 끝점의 좌표는 (sx, sy)이며, 오른쪽 위 끝점의 좌표는 (ex, ey)이다.
3. 볼륨이 V이면, 각 스피커의 음악은 그 스피커와의 거리가 V 이하인 모든 점에서 들을 수 있다.
4. 볼륨은 정수 단위로만 조작 가능하며, 모든 스피커의 볼륨은 같다.
5. 『 예술은 볼륨이다. 』

욱제는 예술의 경지에 다다르기 위한 실험으로 다음과 같은 쿼리를 Q개 준비했다.

• 1 xi yi : (xi, yi)에 스피커를 하나 설치한다. 욱제는 아직 훈련소에 들어가지 않았기 때문에 모든 스피커는 훈련소의 오른쪽 위 바깥에만 설치된다. 즉, ex < xi, ey < yi 가 항상 만족된다.
• 2 Vi : 현재까지 설치된 스피커의 개수가 k개이고, 이들 스피커의 볼륨이 모두 Vi일 때, (훈련소 내부에서 1번 스피커의 음악이 들리는 영역의 넓이) + (훈련소 내부에서 2번 스피커의 음악이 들리는 영역의 넓이) + ... + (훈련소 내부에서 k번 스피커의 음악이 들리는 영역의 넓이) 를 계산하라. 이 값이 정수가 아닐 수도 있으므로, 계산한 값의 2배를 출력하라. 합집합이 아니기 때문에, 한 영역에서 여러 스피커의 소리를 들을 수 있으면 여러 번 센다는 것에 유의하라.

실험들을 해결하고 욱제의 예술(볼륨)을 온 몸으로 느껴보자!

첫째 줄에 훈련소를 나타내는 직사각형의 왼쪽 아래 끝점 (sx, sy)와 오른쪽 위 끝점 (ex, ey)가 주어진다.

둘째 줄에 쿼리의 개수 Q가 주어진다.

셋째 줄부터 Q개의 줄에 걸쳐, i + 2번째 줄에 i번째 쿼리가 주어진다. 2번 쿼리는 한 번 이상 등장한다.

2번 쿼리가 주어질 때마다 한 줄에 하나씩 답을 출력한다. 이 값은 항상 정수이다.

• -100,000 ≤ sx < ex ≤ 0
• -100,000 ≤ sy < ey ≤ 0
• 1 ≤ Q ≤ 250,000
• 1 ≤ xi, yi ≤ 100,000
• 1 ≤ Vi ≤ 400,000
• ex < xi, ey < yi