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 vă dă problema în concurs, poate poate ia o sursă de $100$ de puncte de la voi.

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.

h2. Date de intrare

h2. 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$

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

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

| 10 5
1 10 1 1
1 10 2 5
2 9 3 7
2 6 2 10
1 10 5 10
| 16 18 6 11 13 21 6 8 6 1

|

h3. Explicaţie
 
...
 

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