Pizza Party Planning

You're hosting a festive pizza party with $N$ friends seated around a circular table, numbered from $0$ to $N-1$ in clockwise order. You plan to order $Q$ pizzas over the course of the event. The $i$-th pizza is cut into $a_i$ slices and the very first slice is handed to friend $b_i$. Thereafter, each subsequent slice is passed one seat to the right (clockwise), so that slice number $j$ goes to friend $(b_i + j) \bmod N$.

Your task is to calculate, after all $Q$ pizzas have been fully distributed, the total number of slices each friend has eaten.

Input

The first line contains two integers $N$ and $Q$.

Each of the next $Q$ lines contains two integers $a_i$ and $b_i$, describing the $i$-th pizza.

Output

Print $N$ integers: the total slices received by friend $0$, friend $1$, ... , friend $N-1$, in order, separated by spaces.

Constraints

• $1 \le N, Q \le 2\cdot 10^5$