Bitaro mua một xiên bánh dango dài để ăn vặt. Xiên bánh này được biểu diễn bằng $N$ số nguyên dương $A_1,A_2,\ldots,A_N$ như sau. Với mỗi số nguyên $i$ thỏa mãn $0\le i\le N$, đặt $s_i=A_1+A_2+\cdots+A_i$. Đặc biệt, ta định nghĩa $s_0=0$.
- Xiên gồm $s_N$ viên bánh xếp thành một cột từ trên xuống dưới.
Mỗi viên bánh có vị ngọt hoặc cay. Vị của từng viên được mô tả như sau.
- Nếu $i$ là số lẻ thỏa mãn $1\le i\le N$, các viên bánh từ vị trí $s_{i-1}+1$ đến vị trí $s_i$ tính từ trên xuống có vị ngọt.
- Nếu $i$ là số chẵn thỏa mãn $1\le i\le N$, các viên bánh từ vị trí $s_{i-1}+1$ đến vị trí $s_i$ tính từ trên xuống có vị cay.
Bitaro nghĩ ra $Q$ phương án ăn xiên bánh này. Phương án thứ $j$ ($1\le j\le Q$) được biểu diễn bởi hai số nguyên $L_j,R_j$ thỏa mãn $1\le L_j\le R_j\le N$. Trong phương án này, cậu ăn các viên bánh từ vị trí $s_{L_j-1}+1$ đến vị trí $s_{R_j}$ tính từ trên xuống.
Ngoài ra, Bitaro quyết định chia việc ăn bánh thành nhiều miếng theo cách dưới đây. Ở đây, $K$ là số nguyên dương biểu thị sở thích vị ngọt của Bitaro.
- Cậu ăn bánh từ trên xuống dưới, và mỗi viên được ăn đúng một lần.
- Trong một miếng, cậu có thể ăn một số nguyên dương tùy ý các viên liên tiếp trên xiên. Nếu số viên ngọt trừ số viên cay trong miếng đó ít nhất bằng $K$, Bitaro sẽ cảm thấy hài lòng.
Cho thông tin về xiên bánh và các phương án, hãy viết chương trình tính số lần tối đa Bitaro có thể cảm thấy hài lòng trong từng phương án.
Dữ liệu vào
Đọc dữ liệu sau từ đầu vào chuẩn.
$N\ Q\ K$
$A_1\ A_2\ \cdots\ A_N$
$L_1\ R_1$
$L_2\ R_2$
$\vdots$
$L_Q\ R_Q$
Dữ liệu ra
Ghi $Q$ dòng ra đầu ra chuẩn. Dòng thứ $j$ ($1\le j\le Q$) ghi số lần tối đa Bitaro có thể cảm thấy hài lòng trong phương án thứ $j$.
Giới hạn
- $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$).
- Tất cả các giá trị cho trước đều là số nguyên.
Nhiệm vụ con
- (6 điểm) $Q\le10$.
- (5 điểm) $K\le2$.
- (18 điểm) $K\le10$.
- (27 điểm) $A_1+A_2+\cdots+A_N\le500\,000$.
- (17 điểm) $N\le200\,000,\ Q\le200\,000$.
- (27 điểm) Không có giới hạn bổ sung.
Ví dụ
Dữ liệu vào 1
5 2 1 2 1 2 4 3 1 5 2 4
Dữ liệu ra 1
7 2
Ghi chú
Trong phương án đầu tiên, Bitaro ăn từ viên thứ $1$ đến viên thứ $12$ tính từ trên xuống. Bằng cách ăn lần lượt từ trên xuống, mỗi miếng đúng một viên, cậu có thể hài lòng $7$ lần. Vì không thể khiến cậu hài lòng từ $8$ lần trở lên, cần in $7$.
Trong phương án thứ hai, Bitaro ăn từ viên thứ $3$ đến viên thứ $9$ tính từ trên xuống. Bằng cách ăn lần lượt từ trên xuống, mỗi miếng đúng một viên, cậu có thể hài lòng $2$ lần. Vì không thể khiến cậu hài lòng từ $3$ lần trở lên, cần in $2$.
Ví dụ này thỏa mãn giới hạn của tất cả các nhiệm vụ con.
Dữ liệu vào 2
5 2 3 2 1 2 4 3 1 5 2 4
Dữ liệu ra 2
2 0
Ghi chú
Ví dụ này chỉ khác dữ liệu vào của ví dụ $1$ ở giá trị $K$.
Trong phương án đầu tiên, Bitaro có thể hài lòng $2$ lần bằng cách ăn bánh thành bốn miếng sau.
- Miếng đầu tiên gồm các viên từ thứ $1$ đến thứ $5$ tính từ trên xuống. Có $4$ viên ngọt và $1$ viên cay, nên Bitaro hài lòng.
- Miếng thứ hai chỉ gồm viên thứ $6$ tính từ trên xuống. Có $0$ viên ngọt và $1$ viên cay, nên Bitaro không hài lòng.
- Miếng thứ ba gồm các viên từ thứ $7$ đến thứ $9$ tính từ trên xuống. Có $0$ viên ngọt và $3$ viên cay, nên Bitaro không hài lòng.
- Miếng thứ tư gồm các viên từ thứ $10$ đến thứ $12$ tính từ trên xuống. Có $3$ viên ngọt và $0$ viên cay, nên Bitaro hài lòng.
Vì không thể khiến cậu hài lòng từ $3$ lần trở lên, cần in $2$.
Trong phương án thứ hai, không có cách ăn nào khiến Bitaro hài lòng dù chỉ một lần, nên cần in $0$.
Ví dụ này thỏa mãn giới hạn của các nhiệm vụ con $1,3,4,5,6$.
Dữ liệu vào 3
9 4 50 24 26 89 45 84 72 15 31 66 1 9 2 8 4 6 5 6
Dữ liệu ra 3
3 2 1 1
Ghi chú
Ví dụ này thỏa mãn giới hạn của các nhiệm vụ con $1,4,5,6$.