Problem: Input

The input is given from Standard Input in the following format:


> $N \ Q$ $a_1 \ b_1$ $a_2 \ b_2$ $ ： \ ： $ $a_Q \ b_Q$

Output

* You have to print $N$ lines.
* The $i$-th line should contain the number of dishes of sushi had eaten for customer $i (1 \le i \le N)$.



Constraints

* $3 \le N, Q \le 100,000$
* $1 \le a_i \le N$
* $1 \le b_i \le 10^{12}$
* Any final results do not exceed $2 \times 10^{13}$.



Subtasks

Subtask 1 [ $60$ points ]


* $N, Q \le 100$
* $b_i = 1$

Subtask 2 [ $400$ points ]


* $N, Q \le 100$
* $b_i \le 10^{12}$

Subtask 3 [ $240$ points ]


* $N, Q \le 100,000$
* $b_i = 1$

Subtask 4 [ $500$ points ]


* There are no additional constraints.

Output

* You have to print $N$ lines.
* The $i$-th line should contain the number of dishes of sushi had eaten for customer $i (1 \le i \le N)$.



Constraints

* $3 \le N, Q \le 100,000$
* $1 \le a_i \le N$
* $1 \le b_i \le 10^{12}$
* Any final results do not exceed $2 \times 10^{13}$.



Subtasks

Subtask 1 [ $60$ points ]


* $N, Q \le 100$
* $b_i = 1$

Subtask 2 [ $400$ points ]


* $N, Q \le 100$
* $b_i \le 10^{12}$

Subtask 3 [ $240$ points ]


* $N, Q \le 100,000$
* $b_i = 1$

Subtask 4 [ $500$ points ]


* There are no additional constraints.

Input

The input is given from Standard Input in the following format:


> $N \ Q$ $a_1 \ b_1$ $a_2 \ b_2$ $ ： \ ： $ $a_Q \ b_Q$

Examples

Input

9 3
5 11
8 4
4 7


Output

4
4
4
4
2
2
1
1
0


Input

6 6
3 5
6 11
1 6
4 7
5 2
2 5


Output

10
10
5
5
4
2


Input

5 6
1 1
2 1
3 1
1 1
5 1
3 1


Output

2
2
1
1
0


Input

10 10
10 10
9 20
8 30
7 40
6 50
5 60
4 70
3 80
2 90
1 100


Output

223
123
77
50
33
21
12
7
3
1

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;

ll dat[400000], lazy[400000];
int n = 1;
inline void push(int k, int s) {
	if (lazy[k] == 0)return;
	dat[k] = lazy[k] * s;
	if (k < n - 1) {
		lazy[k * 2 + 1] = lazy[k];
		lazy[k * 2 + 2] = lazy[k];
	}
	lazy[k] = 0;
}
inline void upnode(int k) {
	dat[k] = dat[k * 2 + 1] + dat[k * 2 + 2];
}
inline void update(int a, int b, ll x, int k = 0, int l = 0, int r = n) {
	push(k, r - l);
	if (b <= l || r <= a)return;
	if (a <= l&&r <= b) {
		lazy[k] = x; push(k, r - l); return;
	}
	update(a, b, x, k * 2 + 1, l, (l + r) / 2);
	update(a, b, x, k * 2 + 2, (l + r) / 2, r);
	upnode(k);
}
inline ll query(int a, int b, int k = 0, int l = 0, int r = n) {
	push(k, r - l);
	if (b <= l || r <= a)return 0;
	if (a <= l&&r <= b)return dat[k];
	ll vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
	ll vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
	upnode(k);
	return vl + vr;
}
int main() {
	int N, q; scanf("%d%d", &N, &q);
	while (n < N)n <<= 1;
	rep(i, q) {
		int a; ll b; scanf("%d%lld", &a, &b); a--;
		int l = 0, r = a;
		while (l != r) {
			int t = (l + r) / 2;
			if (query(t, t + 1)*(a - t) - query(t + 1, a + 1) <= b)r = t;
			else l = t + 1;
		}
		b -= query(l, l + 1)*(a - l) - query(l + 1, a + 1);
		update(l, a + 1, query(l, l + 1) + b / (a - l + 1));
		update(l, l + b % (a - l + 1), query(l, l + 1) + 1);
	}
	rep(i, N)printf("%lld\n", query(i, i + 1));
}