cartofi

Fermierul Feder cultivă cartofi pe un teren dreptunghiular de lățime $N$ metri și lungime $M$ metri, compartimentat în $N \times M$ zone pătratice identice de lungime $1$ metru, dispuse alăturat, câte $N$ pe lățime (pe $N$ linii, numerotate de la $1$ la $N$) și câte $M$ pe lungime (pe $M$ coloane, numerotate de la $1$ la $M$).

În fiecare zonă pătratică se află câte o plantă de cartofi. Parcurgând terenul de la prima linie către ultima, fiecare linie cu număr impar parcurgând-o de la coloana $1$ către coloana $M$, iar fiecare linie cu număr par parcurgând-o de la coloana $M$ către coloana $1$, fermierul (pasionat de matematică) a scris numerele cartofilor produși de fiecare plantă, în ordinea parcurgerii, și a constatat că a obținut șirul cifrelor unităților primilor $N \cdot M$ termeni ai șirului Fibonacci (vezi Figura $1$ în care $N = 3$ și $M = 6$).

Cerință

Scrieți un program care citește numerele $N$ și $M$ (cu semnificația din enunț), iar apoi determină:

1. numărul plantelor din teren care nu au produs niciun cartof;
2. numărul maxim de cartofi care pot fi produși de plantele dintr-o suprafață pătratică din terenul fermierului;
3. pentru fiecare dintre cele $Q$ perechi de numere ($A, B$) citite, numărul cartofilor produși de plantele aflate în zonele pătratice situate între coloanele cu numerele $A$ și $B$, inclusiv acestea.

Date de intrare

Fișierul de intrare cartofi.in conține pe prima linie un număr natural $C$ reprezentând cerința din problemă care trebuie rezolvată ($1$, $2$ sau $3$). A doua linie a fișierului conține cele două numere naturale $N$ și $M$, separate printr-un spațiu, cu semnificația din enunț. Dacă $C = 3$, atunci fișierul va mai conține pe a treia linie numărul natural $Q$, iar pe fiecare linie dintre următoarele $Q$, câte două numere naturale separate printr-un spațiu reprezentând câte o pereche de numere ($A, B$) dintre cele $Q$.

Date de ieșire

Fișierul de ieșire cartofi.out va conține:

Dacă $C = 1$, pe prima linie un număr natural reprezentând răspunsul la cerința $1$.
Dacă $C = 2$, pe prima linie un număr natural reprezentând răspunsul la cerința $2$.
Dacă $C = 3$, $Q$ linii, câte o linie pentru fiecare pereche ($A, B$) dintre cele $Q$. Linia corespunzătoare fiecărei perechi ($A, B$) va conține un număr natural reprezentând numărul cartofilor produși de plantele aflate în zonele pătratice situate între coloanele cu numerele $A$ și $B$, inclusiv aceste valori, reprezentând răspunsul la cerința $3$.

Restricții și precizări

• $2 \leq N \leq 500 \ 000 \ 000$;
• $3 \leq M \leq 1 \ 000 \ 000 \ 000$;
• $N \leq M$;
• $Q \leq 100 \ 000$;
• $1 \leq A \leq B \leq M$;
• Pentru cerința 1 se acordă $20$ de puncte, iar pentru cerințele $2$ și $3$ se acordă câte $40$ de puncte.
• Șirul Fibonacci este definit astfel: $f(1) = 1$, $f(2) = 1$ și $f(n) = f(n-1) + f(n-2)$, dacă $n \geq 3$, ($n$ este un număr natural nenul).
• O suprafață pătratică din teren este formată din $K * K$ zone pătratice alăturate dispuse câte $K$ pe linie și câte $K$ pe coloană, oricare ar fi $1 \leq K \leq min(N, M)$;

Exemplul 1

cartofi.in

1
3 6

cartofi.out

1

Explicație

Se rezolvă cerința $1$. $N = 3$, $M = 6$. Primii $N * M$ = $18$ termeni ai șirului Fibonacci sunt: $1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584$. Astfel, numerele cartofilor produși de fiecare plantă din teren sunt cele din Figura $1$. În teren există o singură plantă care nu a produs niciun cartof (cea din linia $3$, coloana $3$).

Exemplul 2

cartofi.in

2
3 6

cartofi.out

42

Explicație

Se rezolvă cerința $2$. $N = 3$, $M = 6$. Numerele cartofilor produși de fiecare plantă din teren sunt cele din tabelul din Figura $1$. Plantele aflate în suprafața pătratică galbenă din tabelul din Figura $2$ au produs cel mai mare număr de cartofi.

Exemplul 3

cartofi.in

3
5 6
3
1 2
4 6
2 3

cartofi.out

48
64
43

Explicație

Se rezolvă cerința $3$. $N = 5$, $M = 6$, $Q = 3$. Tabelul din Figura $3$ conține numerele cartofilor produși de fiecare plantă din teren sunt cele din Figura $3$. Suma elementelor cuprinse între coloanele ($1, 2$), inclusiv $1$ și $2$, este $48$. Suma elementelor cuprinse între coloanele ($4, 6$), inclusiv $4$ și $6$, este $64$. Suma elementelor cuprinse între coloanele ($2, 3$), inclusiv $2$ și $3$, este $43$.