Fişierul intrare/ieşire:	fibo4.in, fibo4.out	Sursă	InfoOltenia 2018 - Clasa a 10-a
Autor	Bogdan Iordache	Adăugată de	Info-Oltenia 2018 •infooltenia
Timp execuţie pe test	2.5 sec	Limită de memorie	262144 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Fibo4

Şirul Fibonacci este şirul dat prin recurenţa:

F₀ = 0, F₁ = 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.

Date de intrare

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.

Date de ieşire

Î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.

Restricţii

• 1 ≤ st ≤ dr ≤ N
• pentru 40% din punctaj: 1 ≤ N, M, k ≤ 1000
• pentru 65% din punctaj 1 ≤ N, M, k ≤ 10⁶
• pentru 80% din punctaj 1 ≤ N, M ≤ 10⁶ şi 1 ≤ k ≤ 10⁹
• pentru 100% din punctaj 1 ≤ N, M ≤ 10⁶ şi 1 ≤ k ≤ 10¹⁸

Exemplu

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₁, elementului de la poziţia 2 i se adună F₂ , ... , elementului de la poziţia 5 i se adună F₅. Obţinem (1, 1, 2, 3, 5).
La a doua operaţie, elementului de la poziţia 2 i se adună F₃, iar elementului de la poziţia 3 i se adună F₄ . Obţinem (1, 3, 5, 3, 5).
La ultima operaţie, elementului de la poziţia 4 i se adună F₆. Obţinem (1, 3, 5, 11, 5).

Cum se trimit solutii?