== include(page="template/taskheader" task_id="fibo4") ==

Şirul Fibonacci este şirul dat prin recurenţa: $F{~0~} = 0, F{~1~} = 1, ..., F{~n~} = F{~n - 1~} + F{~n - 2~}$

Şirul Fibonacci este şirul dat prin recurenţa:
 
$F{~0~} = 0, F{~1~} = 1, ..., F{~n~} = F{~n - 1~} + F{~n - 2~}$
 
După cum probabil aţi ghicit, Fibo este pasionat de şirul Fibonacci, atât de pasionat încât mereu găseşte cele mai interesante probleme legate de acesta. Aşa că nu a ezitat o clipă atunci când l-am rugat să ne sară în ajutor cu o problemă pentru voi. Fibo vă dă un şir de $N$ numere naturale (iniţial toate egale cu $0$), apoi vă roagă să aplicaţi o secvenţă de $M$ operaţii asupra acestuia. O operaţie este de forma $st, dr, k$, cu semnificaţia: pentru fiecare $i$ $(st ≤ i ≤ dr)$, la elementul din şir de la poziţia $i$ se adună F{~k+i-st~}. Fibo vă întreabă cum va arăta şirul după aplicarea celor $M$ operaţii.
 
Cunoscându-se $N$, $M$ şi cele $M$ operaţii, determinaţi configuraţia finală a şirului.

h2. Date de intrare

Fişierul de intrare $fibo4.in$ ...

Prima linie a fişierului $fibo4.in$ va conţine numerele $N$ şi $M$ cu semnificaţia din enunţ.
Pe fiecare dintre următoarele $M$ linii se vor găsi $3$ numere ( $st, dr, k$, cu semnificaţia din enunţ) reprezentând în ordine operaţiile.

h2. Date de ieşire

În fişierul de ieşire $fibo4.out$ ...

În fişierul $fibo4.out$ afişaţi pe prima linie $N$ numere, reprezentând şirul după aplicarea celor $M$ operaţii. Deoarece numerele pot fi mari, afişaţi pe fiecare dintre ele modulo 666013.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ st ≤ dr ≤ N$
* pentru $40%$ din punctaj: $1 ≤ N, M, k ≤ 1000$
* pentru $65%$ din punctaj $1 ≤ N, M, k ≤ 10^6^$
* pentru $80%$ din punctaj $1 ≤ N, M ≤ 10^6^ şi 1 ≤ k ≤ 10^9^$
* pentru $100%$ din punctaj $1 ≤ N, M ≤ 10^6^ şi 1 ≤ k ≤ 10^18^$

h2. Exemplu
table(example). |_. fibo4.in |_. fibo4.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 5 3
  1 5 1
  2 3 3
  4 4 6
| 1 3 5 11 5

|
h3. Explicaţie

...

Şirul iniţial este $(0, 0, 0, 0, 0)$.
 
La prima operaţie, elementului de la poziţia $1$ i se adună $F{~1~}$, elementului de la poziţia $2$ i se adună $F{~2~}$ , ... , elementului de la poziţia $5$ i se adună $F{~5~}$. Obţinem $(1, 1, 2, 3, 5)$.
La a doua operaţie, elementului de la poziţia $2$ i se adună $F{~3~}$, iar elementului de la poziţia $3$ i se adună $F{~4~}$ . Obţinem $(1, 3, 5, 3, 5)$.
La ultima operaţie, elementului de la poziţia $4$ i se adună $F{~6~}$. Obţinem $(1, 3, 5, 11, 5)$.

== include(page="template/taskfooter" task_id="fibo4") ==