Fibo Grid

Gigel are o matrice cu $N$ linii și $M$ coloane în care fiecare celulă conține o cifră. El scrie pe fiecare linie $i$ din matrice (de la stânga la dreapta) al $i$-lea număr fibonacci. Dacă numărul are mai mult de $M$ cifre atunci el scrie doar ultimele $M$ cifre.

De exemplu pentru $N = 13$ și $M = 2$ el va obține matricea:

Cerință

Gigel vă dă $Q$ întrebări de forma $C, L, R$: de câte ori apare cifra $C$ între liniile $L$ și $R$ (inclusiv liniile $L$ și $R$).

Date de intrare

Pe prima linie se afla $N$, $M$ și $Q$.

Pe următoarele $Q$ linii se află query-urile, de forma $(C, L, R)$.

Date de ieșire

Fișierul de ieșire va conține $Q$ linii, pe fiecare linie aflându-se răspunsul corespunzător câte unui query.

Restricții și precizări

• $1 \leq N \leq 10^{17}$
• $1 \leq M \leq 6$
• $1 \leq Q \leq 10^5$
• $0 \leq C \leq 9$
• $1 \leq L \leq R \leq N$
• Gigel vă reamintește ca șirul lui Fibonacci începe cu $1, 1$ și fiecare element este egal cu suma ultimelor două.

Exemplu

stdin

13 2 3
1 1 7
4 8 12
0 1 13

stdout

3
3
6

Explicație

Între liniile 1 și 7 se află 3 cifre de 1, între liniile 8 și 12 se află 3 cifre de 4, iar între liniile 1 și 13 se află 6 cifre de 0.