Bitaro membeli satu tusuk panjang dango sebagai camilan. Tusukan ini dapat dinyatakan dengan $N$ bilangan bulat positif $A_1,A_2,\ldots,A_N$ sebagai berikut. Untuk setiap bilangan bulat $i$ dengan $0\le i\le N$, misalkan $s_i=A_1+A_2+\cdots+A_i$. Secara khusus, kita definisikan $s_0=0$.

• Tusukan terdiri dari $s_N$ butir dango yang tersusun dalam satu kolom dari atas ke bawah.

• Setiap dango memiliki rasa manis atau pedas. Rasanya dijelaskan sebagai berikut.

  • Jika $i$ adalah bilangan ganjil yang memenuhi $1\le i\le N$, maka dango ke-$(s_{i-1}+1)$ hingga ke-$s_i$ dari atas memiliki rasa manis.
  • Jika $i$ adalah bilangan genap yang memenuhi $1\le i\le N$, maka dango ke-$(s_{i-1}+1)$ hingga ke-$s_i$ dari atas memiliki rasa pedas.

Bitaro membuat $Q$ kemungkinan rencana untuk memakan dango tersebut. Rencana ke-$j$ ($1\le j\le Q$) dinyatakan oleh bilangan bulat $L_j,R_j$ dengan $1\le L_j\le R_j\le N$. Dalam rencana ini, ia memakan dango ke-$(s_{L_j-1}+1)$ hingga ke-$s_{R_j}$ dari atas.

Selain itu, Bitaro memutuskan membaginya menjadi beberapa suapan dengan cara berikut. Di sini, $K$ adalah bilangan bulat positif yang menyatakan kesukaan Bitaro terhadap rasa manis.

• Ia memakan dango dari atas ke bawah, dan setiap dango dimakan tepat satu kali.
• Dalam satu suapan, ia boleh memakan berapa pun banyaknya dango berurutan yang positif. Jika jumlah dango manis dikurangi jumlah dango pedas dalam suapan itu setidaknya $K$, Bitaro merasa senang.

Diberikan informasi tusukan dango dan rencana-rencananya, tulislah program yang menghitung jumlah maksimum Bitaro dapat merasa senang untuk setiap rencana.

Masukan

Baca data berikut dari masukan standar.

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

Keluaran

Tuliskan $Q$ baris ke keluaran standar. Pada baris ke-$j$ ($1\le j\le Q$), keluarkan jumlah maksimum Bitaro dapat merasa senang dalam rencana ke-$j$.

Batasan

• $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$).
• Semua nilai yang diberikan adalah bilangan bulat.

Subsoal

1. (6 poin) $Q\le10$.
2. (5 poin) $K\le2$.
3. (18 poin) $K\le10$.
4. (27 poin) $A_1+A_2+\cdots+A_N\le500\,000$.
5. (17 poin) $N\le200\,000$, $Q\le200\,000$.
6. (27 poin) Tidak ada batasan tambahan.

Contoh

Masukan 1

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

Keluaran 1

7
2

Penjelasan

Untuk rencana pertama, Bitaro memakan dango pertama hingga ke-$12$ dari atas. Dengan terus memakan tepat satu dango per suapan dari atas, ia dapat merasa senang tujuh kali. Karena mustahil membuatnya senang delapan kali atau lebih, keluarkan $7$.

Untuk rencana kedua, Bitaro memakan dango ketiga hingga ke-$9$ dari atas. Dengan terus memakan tepat satu dango per suapan dari atas, ia dapat merasa senang dua kali. Karena mustahil membuatnya senang tiga kali atau lebih, keluarkan $2$.

Contoh masukan ini memenuhi batasan semua subsoal.

Masukan 2

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

Keluaran 2

2
0

Penjelasan

Contoh ini berbeda dari Contoh Masukan 1 hanya pada nilai $K$.

Untuk rencana pertama, Bitaro dapat merasa senang dua kali dengan memakan dango dalam empat suapan berikut.

• Suapan pertama memakan dango pertama hingga kelima dari atas. Karena ada empat dango manis dan satu dango pedas, Bitaro merasa senang.
• Suapan kedua hanya memakan dango keenam dari atas. Karena ada nol dango manis dan satu dango pedas, Bitaro tidak merasa senang.
• Suapan ketiga memakan dango ketujuh hingga kesembilan dari atas. Karena ada nol dango manis dan tiga dango pedas, Bitaro tidak merasa senang.
• Suapan keempat memakan dango ke-$10$ hingga ke-$12$ dari atas. Karena ada tiga dango manis dan nol dango pedas, Bitaro merasa senang.

Karena mustahil membuatnya senang tiga kali atau lebih, keluarkan $2$.

Untuk rencana kedua, tidak ada cara memakan dango agar Bitaro merasa senang setidaknya satu kali, sehingga keluarkan $0$.

Contoh masukan ini memenuhi batasan subsoal $1,3,4,5,6$.

Masukan 3

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

Keluaran 3

3
2
1
1

Penjelasan

Contoh masukan ini memenuhi batasan subsoal $1,4,5,6$.