McMartin

Ai, dai, n-ai. Ia nu da, să vezi cum ai.

Într-un viitor nu foarte îndepărtat, orașul era asediat de restaurante fast-food, iar McDonald's devenise un imperiu culinar de neoprit. Însă, în umbră, un erou necunoscut se ridica împotriva acestui gigant – Piedone, un agent de elită al FNCSA.

Cerință

Se dă un șir $a$ de $n$ locații McDonald's, $a_i$ reprezentând numărul de angajați din restaurantul $i$, și un număr $k$.

Piedone numește o pereche $(i, j)$ martin dacă $i < j$ și $(a_i + a_j) \equiv \sum_{p=i+1}^{j-1} a_p \pmod{k}$.

Dându-se $q$ query-uri de tipul $(l, r)$, să se determine pentru fiecare câte perechi martin există astfel încât $l \leq i < j \leq r$.

Date de intrare

Pe prima linie se găsesc două numere întregi, $n$ și $k$.

Pe următoarea linie se află $n$ numere, separate prin câte un spațiu, reprezentând $a_1, a_2, \dots , a_n$.

Pe a treia linie se află un număr $q$, reprezentând numărul de query-uri.

Pe următoarele $q$ linii se află câte 2 numere $l$ și $r$, reprezentând subsecvența din query.

Date de ieșire

Pe primele $q$ linii se vor afla câte un număr, reprezentând răspunsul la fiecare query.

Restricții și precizări

• $1 \leq n, k, q \leq 2 \times 10^5$;
• $1 \leq a_i \leq 10^9$
• $1 \leq l < r \leq n$

Exemplul 1

stdin

7 4
8 2 4 3 1 3 2
3
1 7
2 3
3 7

stdout

5
0
3