Битаро тіскебасар ретінде ұзын бір істік тұшпара сатып алды. Бұл істікті $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$ тұшпарадан тұрады.

• Әрбір тұшпара не тәтті, не ащы болады. Әрбір тұшпараның дәмін келесідей сипаттауға болады.

  • Егер $i$ саны $1\le i\le N$ шартын қанағаттандыратын тақ бүтін сан болса, онда жоғарыдан санағанда $(s_{i-1}+1)$-шіден $s_i$-шіге дейінгі тұшпаралар тәтті болады.
  • Егер $i$ саны $1\le i\le N$ шартын қанағаттандыратын жұп бүтін сан болса, онда жоғарыдан санағанда $(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-шіге дейінгі тұшпараларды жейді. Жоғарыдан бастап әр асағанда дәл бір тұшпарадан қайталап жеу арқылы Битаро 7 рет қуана алады. Оны 8 немесе одан көп рет қуанту мүмкін болмағандықтан, 7 шығару керек.

Екінші жоспар бойынша Битаро жоғарыдан санағанда 3-шіден 9-шыға дейінгі тұшпараларды жейді. Жоғарыдан бастап әр асағанда дәл бір тұшпарадан қайталап жеу арқылы Битаро 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$-ішкі есептердің шектеулерін қанағаттандырады.