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 <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

using namespace std;

typedef long long ll;

const ll INF = 1e18;
const int maxN = 100 * 1000 + 9;

ll segTree[4 * maxN], lazy[4 * maxN];
bool f[4 * maxN];

void propagate(int id, int l, int r){
	if(f[id])
		segTree[id] = lazy[id] * (r - l + 1);
	else 
		segTree[id] += lazy[id] * (r - l + 1);

	if(l != r){
		if(f[id]){
			f[id * 2] = f[id * 2 + 1] = true;
			lazy[id * 2] = lazy[id];
			lazy[id * 2 + 1] = lazy[id];
		} else {
			lazy[id * 2] += lazy[id];
			lazy[id * 2 + 1] += lazy[id];
		}
	}

	lazy[id] = 0;
	f[id] = 0;
}

void upd(int id, int l, int r, int L, int R, ll val, bool changeTo){
	propagate(id, l, r);
	if(L <= l && r <= R){
		lazy[id] = val;
		f[id] = changeTo;
		propagate(id, l, r);
		//cerr << l << ' ' << r << ' ' << segTree[id] << '\n';
		return;
	}
	
	if(r < L || l > R){
		return;
	}

	int mid = (l + r) / 2;
	upd(id * 2, l, mid, L, R, val, changeTo);
	upd(id * 2 + 1, mid + 1, r, L, R, val, changeTo);

	segTree[id] = segTree[id * 2] + segTree[id * 2 + 1];
}

ll getSum(int id, int l, int r, int L, int R){
	propagate(id, l, r);
	if(L <= l && r <= R){
		return segTree[id];
	}

	if(r < L || l > R){
		return 0;
	}
	
	int mid = (l + r) / 2;
	return getSum(id * 2, l, mid, L, R) + getSum(id * 2 + 1, mid + 1, r, L, R);
}

int n, q;

void read(){
	cin >> n >> q;
}

ll aa[maxN];

void brute(){
	while(q--){
		int r; ll p;  cin >> r >> p;
		ll tot = 0;
		ll foo = -1;
		for(int i = r; i > 0; i--){
			int len = r - i + 1;
			tot += aa[i];
			if(p - (aa[i] * len - tot) >= 0){
				foo = i;
			}
		}

		for(int i = r; i > foo; i--){
			p -= (aa[foo] - aa[i]);
			aa[i] = aa[foo];
		}

		int P = p / (r - foo + 1);
		int Q = p % (r - foo + 1);
		for(int i = foo; i <= r; i++){
			aa[i] += P;
		}
		
		//cerr << foo << ' ' << P << ' ' << Q << '\n';

		//for(int i = 1; i <= n; i++){
		//	cerr << aa[i] << ' ';
		//}
		//cerr << '\n';

		for(int i = foo; i <= foo + Q - 1; i++){
			aa[i]++;
		}

		//for(int i = 1; i <= n; i++){
		//	cerr << aa[i] << ' ';
		//}
		//cerr << '\n';
	}

	for(int i = 1; i <= n; i++){
		cout << aa[i] << ' ';
	}
	cout << '\n';
}

void better(){
	while(q--){
		int r; ll p;  cin >> r >> p;
		int lo = 1, hi = r, foo = r;
		while(lo <= hi){
			int mid = (lo + hi) / 2;
			if(p - ((r - mid + 1) * getSum(1, 1, n, mid, mid) - getSum(1, 1, n, mid, r)) >= 0){
				foo = mid;
				hi = mid - 1;
			} else {
				lo = mid + 1;
			}
		}

		ll x = getSum(1, 1, n, foo, foo);
		p -= ((r - foo + 1) * x - getSum(1, 1, n, foo, r));

		upd(1, 1, n, foo, r, x, true);
		//cerr << foo << ", " << r << " = " << x << '\n';
		//for(int i = 1; i <= n; i++){
		//	cout << getSum(1, 1, n, i, i) << ' ';
		//}
		//cout << '\n';
		
		ll P = p / (r - foo + 1);
		int Q = p % (r - foo + 1);
		upd(1, 1, n, foo, r, P, false);
		//for(int i = 1; i <= n; i++){
		//	cout << getSum(1, 1, n, i, i) << ' ';
		//}
		//cout << '\n';

		upd(1, 1, n, foo, foo + Q - 1, 1, false);
		//for(int i = 1; i <= n; i++){
		//	cout << getSum(1, 1, n, i, i) << ' ';
		//}
		//cout << '\n';
		//cout << "\n\n\n";
	}

	for(int i = 1; i <= n; i++){
		cout << getSum(1, 1, n, i, i) << '\n';
	}
}

void solv(){
	//if(n <= 2000){
	//	brute();
	//} else {
	//	better();
	//}

	better();
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
#ifdef h4h4
	freopen((FILENAME + ".inp").c_str(), "r", stdin);
	freopen((FILENAME + ".out").c_str(), "w", stdout);
#endif
	
	read();
	solv();

	return 0;
}