비타로는 간식으로 긴 경단 꼬치 하나를 샀습니다. 이 꼬치는 $N$개의 양의 정수 $A_1,A_2,\ldots,A_N$으로 다음과 같이 나타낼 수 있습니다. $0\le i\le N$을 만족하는 각 정수 $i$에 대해 $s_i=A_1+A_2+\cdots+A_i$라고 합시다. 특히 $s_0=0$으로 정의합니다.

• 꼬치는 위에서부터 아래로 일렬로 꽂혀 있는 $s_N$개의 경단으로 이루어져 있습니다.

• 각 경단은 달콤한 맛 또는 매운맛 중 하나입니다. 각 경단의 맛은 다음과 같이 설명할 수 있습니다.

  • $1\le i\le N$을 만족하는 홀수 정수 $i$에 대해, 위에서부터 $(s_{i-1}+1)$번째부터 $s_i$번째까지의 경단은 달콤한 맛입니다.
  • $1\le i\le N$을 만족하는 짝수 정수 $i$에 대해, 위에서부터 $(s_{i-1}+1)$번째부터 $s_i$번째까지의 경단은 매운맛입니다.

이 경단 꼬치를 먹을 때 비타로는 $Q$가지 가능한 계획을 세웠습니다. $j$번째 계획 ($1\le j\le Q$)은 $1\le L_j\le R_j\le N$을 만족하는 정수 $L_j$와 $R_j$로 나타내어지며, 이 계획에서 그는 위에서부터 $(s_{L_j-1}+1)$번째부터 위에서부터 $s_{R_j}$번째까지의 경단을 먹습니다.

또한 이 꼬치를 먹을 때 비타로는 다음과 같은 방법으로 여러 번의 한 입으로 나누어 먹기로 했습니다. 여기서 $K$는 단맛에 대한 비타로의 선호도를 나타내는 양의 정수입니다.

• 경단을 위에서부터 아래로 순서대로 먹으며, 각 경단은 정확히 한 번씩 먹습니다.
• 한 입에는 꼬치에 연속해 있는 임의의 양의 개수의 경단을 먹을 수 있습니다. 만약 그 한 입에 먹은 경단들 중 달콤한 경단의 개수에서 매운 경단의 개수를 뺀 값이 $K$ 이상이면, 비타로는 기분이 좋아집니다.

경단 꼬치에 대한 정보와 계획들이 주어졌을 때, 각 계획에 대해 비타로가 기분이 좋아질 수 있는 최대 횟수를 구하는 프로그램을 작성하십시오.

입력

표준 입력에서 다음 데이터를 읽으십시오.

$$ \begin{array}{l} N\ Q\ K\\ A_1\ A_2\ \cdots\ A_N\\ L_1\ R_1\\ L_2\ R_2\\ \vdots\\ L_Q\ R_Q \end{array} $$

출력

표준 출력에 $Q$개의 줄을 출력하십시오. $j$번째 줄 ($1\le j\le Q$)에는 $j$번째 계획에서 비타로가 기분이 좋아질 수 있는 최대 횟수를 출력합니다.

제약 조건

• $1\le N\le500\,000$.
• $1\le Q\le500\,000$.
• $1\le K\le10^{14}$.
• $1\le A_i\le10^9$ ($1\le i\le N$).
• $1\le L_j\le R_j\le N$ ($1\le j\le Q$).
• 주어지는 값은 모두 정수입니다.

서브태스크

1. (6점) $Q\le10$.
2. (5점) $K\le2$.
3. (18점) $K\le10$.
4. (27점) $A_1+A_2+\cdots+A_N\le500\,000$.
5. (17점) $N\le200\,000$, $Q\le200\,000$.
6. (27점) 추가 제약 조건 없음.

예제

입력 1

5 2 1
2 1 2 4 3
1 5
2 4

출력 1

7
2

노트

첫 번째 계획에서 비타로는 위에서부터 1번째부터 12번째까지의 경단을 먹습니다. 위에서부터 한 입에 경단을 정확히 1개씩 반복해서 먹으면 비타로는 7번 기분이 좋아질 수 있습니다. 8번 이상 기분이 좋아지게 하는 것은 불가능하므로 7을 출력해야 합니다.

두 번째 계획에서 비타로는 위에서부터 3번째부터 9번째까지의 경단을 먹습니다. 위에서부터 한 입에 경단을 정확히 1개씩 반복해서 먹으면 비타로는 2번 기분이 좋아질 수 있습니다. 3번 이상 기분이 좋아지게 하는 것은 불가능하므로 2를 출력해야 합니다.

이 예제 입력은 모든 서브태스크의 제약 조건을 만족합니다.

입력 2

5 2 3
2 1 2 4 3
1 5
2 4

출력 2

2
0

노트

이 예제는 예제 입력 1에서 $K$의 값만 다릅니다.

첫 번째 계획에서 비타로는 다음과 같이 네 번의 한 입으로 경단을 먹음으로써 2번 기분이 좋아질 수 있습니다.

• 첫 번째 한 입에는 위에서부터 1번째부터 5번째까지의 경단을 먹습니다. 달콤한 경단의 개수가 4개이고 매운 경단의 개수가 1개이므로 비타로는 기분이 좋아집니다.
• 두 번째 한 입에는 위에서부터 6번째 경단만 먹습니다. 달콤한 경단의 개수가 0개이고 매운 경단의 개수가 1개이므로 비타로는 기분이 좋아지지 않습니다.
• 세 번째 한 입에는 위에서부터 7번째부터 9번째까지의 경단을 먹습니다. 달콤한 경단의 개수가 0개이고 매운 경단의 개수가 3개이므로 비타로는 기분이 좋아지지 않습니다.
• 네 번째 한 입에는 위에서부터 10번째부터 12번째까지의 경단을 먹습니다. 달콤한 경단의 개수가 3개이고 매운 경단의 개수가 0개이므로 비타로는 기분이 좋아집니다.

3번 이상 기분이 좋아지게 하는 것은 불가능하므로 2를 출력해야 합니다.

두 번째 계획에서는 비타로가 적어도 한 번 이상 기분이 좋아지도록 경단을 먹는 것이 불가능하므로 0을 출력해야 합니다.

이 예제 입력은 서브태스크 $1,3,4,5,6$의 제약 조건을 만족합니다.

입력 3

9 4 50
24 26 89 45 84 72 15 31 66
1 9
2 8
4 6
5 6

출력 3

3
2
1
1

노트

이 예제 입력은 서브태스크 $1,4,5,6$의 제약 조건을 만족합니다.