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:
//start:
//finish:
#include<bits/stdc++.h>
#define maxn 100005
using namespace std;
typedef long long ll;
ll a[maxn*4],flag[maxn*4]; 
int n,Q;
void down(int x,int l,int r){
	int mid=(l+r)/2;
	if(!flag[x])return;
	flag[x*2]=flag[x];flag[x*2+1]=flag[x];
	a[x*2]=1ll*flag[x]*(mid-l+1);
	a[x*2+1]=1ll*flag[x]*(r-mid);
	flag[x]=0;
}
ll query(int x,int l,int r,int tx,int ty){
	if(l>=tx && r<=ty)return a[x];
	down(x,l,r);
	ll ret=0,mid=(l+r)>>1;
	if(mid>=tx)ret+=query(x*2,l,mid,tx,ty);
	if(mid<ty)ret+=query(x*2+1,mid+1,r,tx,ty);
	return ret;
}
void modify(int x,int l,int r,int tx,int ty,ll val){
	if(l>=tx && r<=ty){
		flag[x]=val;
		a[x]=1ll*(r-l+1)*val;return;
	}
	int mid=(l+r)/2;down(x,l,r);
	if(mid>=tx)modify(x*2,l,mid,tx,ty,val);
	if(mid<ty)modify(x*2+1,mid+1,r,tx,ty,val);
	a[x]=a[x*2]+a[x*2+1];
}

int main(){
	scanf("%d%d",&n,&Q);
	while(Q--){
		int x;ll y;
		scanf("%d%lld",&x,&y);
		if(x==1){
			modify(1,1,n,1,1,query(1,1,n,x,x)+y);
			continue;
		}
		if(query(1,1,n,x-1,x-1)-query(1,1,n,x,x)>=y){
			modify(1,1,n,x,x,query(1,1,n,x,x)+y);continue;
		}
		int l=2,r=x,pos;
		while(l<=r){
			int mid=(l+r)/2;
			if(query(1,1,n,mid-1,mid-1)*(x-mid+1)-query(1,1,n,mid,x)<=y){
				pos=mid;r=mid-1;
			}
			else{
				l=mid+1;
			}
		}
	//	cout<<" "<<pos<<" "<<query(1,1,n,1,1)<<endl;
		ll val=query(1,1,n,pos-1,pos-1);
		ll he=query(1,1,n,pos,x);
		modify(1,1,n,pos,x,val);
		y-=val*(x-pos+1)-he;
		int num=x-pos+2;
		if(y/num){
			modify(1,1,n,pos-1,x,val+y/num);
		}
		if(y%num){
			modify(1,1,n,pos-1,pos-2+y%num,val+y/num+1);
		}
	}
	for(int i=1;i<=n;i++){
		printf("%lld\n",query(1,1,n,i,i));
	}
	return 0;
}