fibopower

Se consideră șirul numerelor Fibonacci $1$, $1$, $2$, $3$, $5$, $8$, $13$, $21$, $34$, $55$, $89$, $\dots$

Șirul este definit astfel:

• $fib[1] = 1$, $fib[2] = 1$
• $fib[i] = fib[i - 1] + fib[i - 2]$, unde $fib[i]$ reprezintă al $i$-lea număr Fibonacci.

Spunem că un număr natural $x$ este fibopower dacă acesta se poate descompune în produs de trei numere Fibonacci distincte.

Exemplu: numărul $48$ este un număr fibopower deoarece $48 = 2 \cdot 3 \cdot 8$.

Se consideră șirul $A = (A_1, A_2, \dots A_n)$ cu $n$ elemente numere naturale nenule, respectiv un număr natural $k$ cuprins între $1$ și $n$. O secvență a șirului $A$ este formată din valori situate pe poziții consecutive în $A$: $A_i, A_{i+1}, \dots A_j$, unde $1 \leq i \leq j \leq n$.

Pe șirul $A$ se fac $q$ interogări de tipul $x$ $y$ cu semnificația: să se determine numărul secvențelor $A_i, A_{i+1}, \dots A_j$ cu $x \leq i \leq j \leq y$ care conțin exact $k$ numere fibopower.

Cerință

Fiind cunoscute $n$, $k$, $q$ și cele $n$ elemente ale șirului $A$, să se determine răspunsul pentru cele $q$ interogări date.

Date de intrare

Fișierul de intrare fibopower.in conține pe prima linie numerele naturale $n$, $k$ și $q$, cu semnificația din enunț. Pe a doua linie se află $n$ numere naturale nenule ce reprezintă elementele șirului $A$. Pe următoarele $q$ linii, sunt scrise cele $q$ interogări, câte o interogare pe o linie, sub forma a două numere naturale $x$ $y$, cu semnificația din enunț. Valorile scrise pe aceeași linie sunt separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire fibopower.out conține $q$ linii, pe linia $i$ ($1 \leq i \leq q$) fiind scris răspunsul la cea de a $i$-a interogare din fișierul de intrare.

Restricții și precizări

• $1 \leq n \leq 10^5$
• $1 \leq q \leq 10^5$
• $1 \leq k \leq n$
• $1 \leq A_i \leq 10^9$, pentru $1 \leq i \leq n$
• Pentru orice întrebare $1 \leq x \leq y \leq n$

Exemplu

fibopower.in

6 2 2
5 6 21 48 6 9
1 6
2 5

fibopower.out

6
3

Explicație

$n = 6$, $k = 2$

În șir există $3$ numere fibopower: $A_2$, $A_4$, $A_5$

Avem de rezolvat $2$ interogări.

La prima interogare trebuie să determinăm câte secvențe aflate între pozițiile $1, 6$ în șir conțin exact $2$ numere fibopower. Sunt $6$ astfel de secvențe:

• $5$ $6$ $21$ $48$
• $6$ $21$ $48$
• $21$ $48$ $6$
• $21$ $48$ $6$ $9$
• $48$ $6$
• $48$ $6$ $9$

La a doua interogare răspunsul este $3$, cele $3$ secvențe fiind:

• $6$ $21$ $48$
• $21$ $48$ $6$
• $48$ $6$