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 $ab$. Se cere să se afișeze pentru fiecare query $f_a$, $f_b$ și suma elementelor $f_k$ din șirul lui Fibonacci cu $a\le k\le 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.