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>
using namespace std;
#define int long long

map<int,int> data;

int counter(int idx){
	auto nx = data.upper_bound(idx);
	auto it = --nx;
	return it->second;
}

void debug(){
	for( auto i : data ) cout << i.first << " " << i.second << endl;
	cout << "_____" << endl;
}
int query(int idx,int b){
	//cout << idx << " " << b << endl;
	//cout << "++++" << endl;
	//debug();
	
	auto nx = data.upper_bound(idx);
	auto it = nx;--it;
	//cout << it->first << endl;
	//cout << b+1 << " " << nx->first << endl;
	if( idx+1 < nx->first ){
		data[idx+1] = it->second;
	}
	auto nx2 = data.upper_bound(idx);
	int len = nx2->first - it->first;
	auto pr = it;
	pr--;
	int diff = pr->second - it->second;
	//cout << diff << "<<" << endl;
	if( pr->first >= 0 and diff * len <= b ){
		data.erase(it);
		return b - diff * len;
	}else{
		int all = b / len;
		int part = b % len;
		//cout << all << " " << part << endl;
		if( all + 1 == pr->second ){
			if( part ){
				data[it->first+part] = it->second + all;
				data.erase(it);
			}else{
				it->second = it->second + all;
			}
		}else{
			if(part){
				data[it->first+part] = it->second + all;
				it->second = it->second + all + 1;
			}else{
				it->second = it->second + all;
			}
		}
		return 0;
	}
}
signed main(){
	ios::sync_with_stdio(false);
	int N,Q;
	cin >> N >> Q;
	data[-1] = 1e18;
	data[0] = 0;
	data[N] = -1;
	
	for(int i = 0 ; i < Q ; i++){
		int a,b;
		cin >> a >> b;
		--a;
		while(b = query(a,b));

	}
	
	for(int i = 0 ; i < N ; i++){
		cout << counter(i) << endl;
	} 
}