당신은 높이가 $[0, d]$ 범위에 속하는 로봇을 만들 수 있는 능력이 있습니다. 로봇들을 테스트하기 위해, 몇 개의 장애물이 포함된 길이 $n$의 직선 코스를 건설했습니다. 장애물에 대한 정보는 배열 $a$로 주어집니다. 만약 $a_i = 0$이면 $i$번째 위치에는 장애물이 없으며, 그렇지 않으면 높이가 $a_i > 0$인 장애물이 있습니다.
로봇을 테스트하기 위해 구간 $[l, r]$을 선택하고 그 구간에 포함된 모든 장애물을 통과하게 합니다. 로봇이 값이 $a_i > 0$인 장애물을 만나면 다음 두 가지 경우 중 하나가 발생합니다:
- 로봇의 현재 높이 $h$가 $a_i$보다 작으면, 로봇이 너무 낮아 장애물에 닿지 않으므로 아무 일도 일어나지 않습니다.
- 로봇의 현재 높이 $h$가 $a_i$ 이상이면, 새로운 높이는 $h' = h - a_i$로 바뀝니다.
이제 $q$개의 질의에 답해야 합니다. $q$개의 구간 $[l_i, r_i]$ 각각에 대해, 초기 높이를 구간 $[0, d]$에서 선택했을 때 구간 내의 장애물들을 모두 통과한 후 로봇이 가질 수 있는 최대 최종 높이를 구하세요.
입력
첫째 줄에 정수 $n, q, d$ ($1 \le n, q \le 3 \cdot 10^5, 1 \le d \le 10^9$)가 주어집니다 — 배열의 길이와 질의의 개수입니다.
둘째 줄에 $n$개의 정수 $a_i$ ($0 \le a_i \le 10^9$)가 주어집니다 — 배열에 대한 설명입니다.
다음 $q$개의 줄에는 정수 쌍 $[l_i, r_i]$ ($1 \le l_i \le r_i \le n$)가 주어집니다 — 질의에 대한 설명입니다.
출력
$q$개의 정수를 출력합니다 — 각 질의에 대한 답입니다.
예제
입력 1
5 3 5 0 2 6 1 3 5 5 1 5 1 3
출력 1
2 2 3
입력 2
7 5 10 7 6 2 5 0 1 4 1 3 1 7 4 7 2 5 4 6
출력 2
3 2 3 3 4