Cerința

Se dă șirul lui Fibonacci: \({f}_{1}=1\), \({f}_{2}=1\), \({f}_{3}=2\), \({f}_{4}=3\), \({f}_{5}=5\), …, definit astfel \({f}_{k+2}\) = \({f}_{k+1}\) + \({f}_{k}\), \(k>2\).

Se dau \(Q\) query-uri de forma \(a b\). Se cere să se afișeze pentru fiecare query \({f}_{a}\), \({f}_{b}\) și suma elementelor \({f}_{k}\) din șirul lui Fibonacci cu \(a≤k≤b\).

Date de intrare

Fișierul de intrare fibointerval.in conține pe prima linie numerele n si Q, iar pe următoarele Q linii câte două numere a si b reprezentând query-urile.

Date de ieșire

Fișierul de ieșire fibointerval.out va conține pe fiecare linie, în ordine, rezultatul celor Q query-uri, cele 3 valori care trebuie afișate fiind separate prin câte un spațiu.

Restricții și precizări

• 1 ≤ n ≤ 1000
• 1 ≤ Q ≤ 10000
• 1 ≤ a ≤ b ≤ n

Exemplu:

fibointerval.in

10 3
1 3
3 5
2 8

fibointerval.out

1 2 4
2 5 10
1 21 53

Explicație

\(n=10\) și \(Q=3\).
Primul query: \(a=1\), \(b=3\), rezultă că \({f}_{1}=1\), \({f}_{3}=2\), iar suma elementelor cu indici cuprinși intre \(a\) și \(b\) este 4.
Al doilea query: \(a=3\), \(b=5\), rezultă că \({f}_{3}=2\), \({f}_{5}=5\), iar suma elementelor cu indici cuprinși intre \(a\) și \(b\) este 10.
Al treilea query: \(a=2\), \(b=8\), rezultă că \({f}_{2}=1\), \({f}_{8}=21\), iar suma elementelor cu indici cuprinși intre \(a\) și \(b\) este 53.