Fermierul Feder cultivă cartofi pe un teren dreptunghiular de lățime N metri și lungime M metri, compartimentat în N * 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 * M termeni ai șirului Fibonacci (vezi Figura 1 în care N = 3 și M = 6).

Cerința

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 ≤ N ≤ 500.000.000
3 ≤ M ≤ 1.000.000.000
N ≤ M
Q ≤ 100.000
1 ≤ A ≤ B ≤ M
Pentru cerința 1 se acordă 20p, iar pentru cerințele 2 și 3 se acordă câte 40p.
Șirul Fibonacci este definit astfel: f(1) = 1, f(2) = 1 și f(n) = f(n-1) + f(n-2), dacă n ≥ 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 ≤ K ≤ min{N, M}.

Exemplul 1:

cartofi.in

1
3 6

cartofi.out

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

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

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.

#include <bits/stdc++.h>
using namespace std;
ifstream f("cartofi.in");
ofstream g("cartofi.out");
pair<int, int> fibo(long long n)
{
if (n == 0)
return {0, 1};
auto p = fibo(n >> 1ll);
int ax = ((p.second << 1) - p.first + 10) % 10;
int c = (p.first * ax) % 10;
int d = (p.first * p.first + p.second * p.second) % 10;
if (n & 1)
return {d, (c + d) % 10};
return {c, d}; }
int n, m;
long long cols[61];
long long query(int);
void build();
void solve1();
void solve2();
void solve3();
int32_t main()
{
int task;
f >> task >> n >> m;
if (task == 1)
solve1();
else if (task == 2)
solve2();
else
solve3();
return 0;
}
void solve1()
{
long long ct = 0, ax = (1ll * n * m) / 60ll, ap = (1ll * n * m) % 60ll;
 long long rez = 0;
for (int i = 0, a = 0, b = 1, c; i < 60; i++)
{
ct += !b;
if (i < ap)
rez += !b;
c = (a + b) % 10;
a = b;
b = c;
}
rez += 1ll * ax * ct;
g << rez;
} 
void solve2()
{
build();
long long rez = 0, ax;
for (int i = n; i <= min(n + 60, m); i++)
{
ax = query(i) - query(i - n);
rez = max(rez, ax);
}
g << rez;
}
void solve3()
{
build();
int q, st, dr;
for (f >> q; q; q--)
{
f >> st >> dr;
g << (long long)query(dr) - query(st - 1) << '\n';
}
}
void build()
{
long long aux[61], prv = 0, md = n % 60, ct = n / 60, ind;
memset(aux, 0, sizeof aux);
for (int i = 0, nr; i < min(n, 60); i++, prv += m)
for (int j = 1; j <= min(m, 60); j++)
{
ind = prv;
if (i & 1)
ind += m - j + 1;
else
ind += j;
nr = fibo(ind).first;
cols[j] += nr;
if (i < md)
aux[j] += nr;
}
for (int i = 1; i <= min(m, 60); i++)
cols[i] = 1ll * cols[i] * ct + aux[i], cols[i] += cols[i - 1];
}
long long query(int poz)
{
long long rez = 1ll * (poz / 60) * cols[60];
rez += cols[poz % 60];
return rez;
}