Fişierul intrare/ieşire:	mayonaka.in, mayonaka.out	Sursă	Algoritmiada 2016 - Runda 2, Juniori
Autor	Eugenie Daniel Posdarascu, Mihai Calancea	Adăugată de	Mihai Calancea •klamathix
Timp execuţie pe test	0.4 sec	Limită de memorie	100000 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Mayonaka

Eudanip nu şi-a rezolvat problemele de implementare care-l bântuie de atâţia ani. Pentru a se ascunde de ruşinea publică cauzată de acest fapt, el s-a stabilit în Australia, unde lucrează la un centru de studiu al cangurilor. Specialiştii în canguri încearcă să studieze cum se schimbă greutatea cangurilor în timp. În acest scop, ei au împărţit o anumită cărare pe care călătoresc deseori canguri în N celule. Fiecare din cele N celule conţine un cântar, care va însuma masa tuturor cangurilor care păşesc pe celula respectivă. Un cangur poate fi descris succint printr-un tuplu x, y, salt, greutate. El va începe călătoria pe celula x şi va păşi pe celulele x + k * salt pentru toţi k non-negativi pentru care x + k * salt ≤ y.

Dându-se un N şi o listă de M canguri, Eudanip trebuie să afle suma înregistrată pe fiecare cântar după încheierea tuturor călătoriilor. El ştie să facă asta, dar a decis să vă propună vouă problema în concurs, poate poate ia o sursă de 100 de puncte de la voi.

Date de intrare

Fişierul de intrare mayonaka.in va conţine pe prima sa linie numerele N şi M, având semnificaţia din enunţ. Următoarele M linii vor conţine câte 4 numere x, y, salt, greutate având semnificaţia din enunţ.

Date de ieşire

În fişierul de ieşire mayonaka.out va conţine N numere, reprezentând sumele înregistrate de fiecare cântar.

Restricţii

• 1 ≤ N, M ≤ 100.000
• 1 ≤ x[i] ≤ y[i] ≤ N
• 1 ≤ salt[i] ≤ N - 1
• 1 ≤ greutate[i] ≤ 10.000
• Pentru teste in valoare de 30 de puncte N, M ≤ 5.000
• Pentru teste in valoare de 70 de puncte N, M ≤ 70.000

Exemplu

Cum se trimit solutii?