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.