34985번 - 해안 경비 스페셜 저지

문제

모그는 여름을 맞아 해안가로 놀러 왔다. 해안은 가로 길이가 $W$인 육지와 바다로 이루어져 있으며, 바다는 육지로부터 정확히 거리 $H$만큼 떨어진 지점까지 이어진다. 바다의 끝에는 직선 형태의 부표줄이 설치되어 있다. 이를 좌표평면으로 나타내면, 부표줄은 점 $(0, 0)$과 $(W, 0)$을 잇는 선분으로 표현되며, 바다는 0ドル \le x \le W, 0 \le y \le H$를 만족하는 직사각형 영역이다.

바다와 육지의 경계에는 사람들의 안전을 책임지는 $N$명의 경비대원이 왼쪽에서부터 차례대로 배치되어 있다. 즉, $i$번째 경비대원의 위치는 좌표평면 상의 점 $(x_i, H)$이다. 각 경비대원은 자신의 위치에서 부표줄의 왼쪽 끝부터 오른쪽 끝까지 바라볼 수 있으며, 이때 형성되는 삼각형 형태의 바다 영역을 감시할 수 있다. 다시 말해, 경비대원은 세 점 $(x_i, H),$ $(0, 0),$ $(W, 0)$을 잇는 삼각형의 내부 전체를 감시한다.

이러한 경비대원들의 감시 영역이 서로 겹칠 수 있다는 점에 착안한 모그는, 특정 경비대원들만 존재할 때 이들이 감시할 수 있는 바다 영역의 전체 넓이가 얼마나 되는지 궁금해졌다. 이에 모그는 총 $Q$개의 질문을 하게 되며, 각 질문은 다음과 같은 형식이다.

• $l\ r$: $l, l+1, \cdots, r$번 경비대원만 존재할 때, 이들이 감시할 수 있는 바다 영역의 전체 넓이를 구하라.

궁금증이 많은 모그를 위해 모그의 질문에 답해주자.

입력

첫번째 줄에 양의 정수 $W, H$가 공백으로 구분되어 주어진다. $(1\le W, H\le 10^9)$

두번째 줄에 경비대원의 수를 뜻하는 양의 정수 $N$이 주어진다. $(1\le N\le 2\times 10^5)$

세번째 줄에 정수 $x_1, x_2, \cdots, x_N$이 공백으로 구분되어 주어진다. $x_i$는 $i$번째 경비대원의 위치를 뜻한다. $(0\le x_1<x_2<\cdots<x_N\le W)$

네번째 줄에 모그가 할 질문의 수를 뜻하는 양의 정수 $Q$가 주어진다. $(1\le Q\le 2\times 10^5)$

다섯번째 줄부터 $Q$개의 줄에 걸쳐 양의 정수 $l, r$이 공백으로 구분되어 주어진다. $(1\le l\le r\le N)$

출력

$Q$개의 줄에 걸쳐 각 질문에 대한 답을 출력한다. 상대/절대 오차는 10ドル^{-6}$까지 허용된다.

제한

노트