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 <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <set>
#include <iostream>
using namespace std;
set<pair<int,long long > >st;
int n;
void output(){
	    auto it=st.begin();
		int i=1;
		while(i<=n){
			if(i<=it->first){
				cout<<it->second<<endl;
				++i;
			}
			else{
				++it;
			}
		}
}
int main(){
	int Q;
	scanf("%d%d",&n,&Q);
	st.insert(make_pair(n,0));
	while(Q--){
		int a;
		long long b;
		cin>>a>>b;
		while(b){
			auto it=st.lower_bound(make_pair(a,-1));
			if(it==st.begin()){
				int pos=it->first;
				long long val=it->second+b/a;
				if(pos==a){
					st.erase(it);
					st.insert(make_pair(a,val));
				}
				else{
					st.insert(make_pair(a,val));
				}
				b%=a;
				if(b){
					st.insert(make_pair(b,val+1));
					b=0;
				}

			}
			else{
				auto it0=it;
				--it0;
				//cout<<it->first<<" "<<it->second<<endl;
				//cout<<it0->first<<" "<<it0->second<<endl;
				int len=a-it0->first;
				long long tot=(it0->second-it->second)*len;
				if(b>=tot){
					b-=tot;
					long long cur=it->second+tot/len;
					if(a==it->first){
						st.erase(it);
						st.insert(make_pair(a,cur));
						st.erase(it0);
					}
					else{
						st.erase(it0);
						st.insert(make_pair(a,cur));
					}
				}
				else{
					long long add=b/len+it->second;
					if(a==it->first){
						st.erase(it);
						st.insert(make_pair(a,add));
					}
					else{
						st.insert(make_pair(a,add));
					}
					b%=len;
					if(b){
						st.insert(make_pair(it0->first+b,add+1));
					}
					b=0;
				}
			}
		}
	}
	output();
	//system("pause");
	return 0;
}