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>
#pragma GCC optimize ("Ofast")
using namespace std;
long n,q,idx;
long long val,lazy[1000005],st_max[1000005],st_sum[1000005];
void update(long id,long l,long r,long i,long j,long long x){
	if(lazy[id]!=0){
		st_max[id]=lazy[id];
		st_sum[id]=(r-l+1)*lazy[id];
		if(l<r){
		    lazy[2*id]=lazy[id];
		    lazy[2*id+1]=lazy[id];
		}
		lazy[id]=0;
	}
	if(l>j||r<i||i>j){
		return;
	}
	if(l>=i&&r<=j){
		st_max[id]=x;
		st_sum[id]=(r-l+1)*x;
		if(l<r){
		    lazy[2*id]=x;
		    lazy[2*id+1]=x;
		}    
		return;
	}
	long mid=(l+r)/2;
	update(2*id,l,mid,i,j,x);
	update(2*id+1,mid+1,r,i,j,x);
	st_max[id]=max(st_max[2*id],st_max[2*id+1]);
	st_sum[id]=st_sum[2*id]+st_sum[2*id+1];
}
long long get_max(long id,long l,long r,long i,long j){
	if(lazy[id]!=0){
		st_max[id]=lazy[id];
		st_sum[id]=(r-l+1)*lazy[id];
		if(l<r){
		    lazy[2*id]=lazy[id];
		    lazy[2*id+1]=lazy[id];
		}
		lazy[id]=0;
	}
	if(l>j||r<i||i>j){
		return -1e18;
	}
	if(l>=i&&r<=j){
		return st_max[id];
	}
	long mid=(l+r)/2;
	return max(get_max(2*id,l,mid,i,j),get_max(2*id+1,mid+1,r,i,j));
}
long long get_sum(long id,long l,long r,long i,long j){
	if(lazy[id]!=0){
		st_max[id]=lazy[id];
		st_sum[id]=(r-l+1)*lazy[id];
		if(l<r){
		    lazy[2*id]=lazy[id];
		    lazy[2*id+1]=lazy[id];
		}
		lazy[id]=0;
	}
	if(l>j||r<i||i>j){
		return 0;
	}
	if(l>=i&&r<=j){
		return st_sum[id];
	}
	long mid=(l+r)/2;
	return get_sum(2*id,l,mid,i,j)+get_sum(2*id+1,mid+1,r,i,j);
}
long search(long l,long r,long i,long long val){
	while(l<r){
		long mid=(l+r)/2;
		if((get_max(1,1,n,mid,i)*(i-mid+1)-get_sum(1,1,n,mid,i))<=val){
			r=mid;
		}else{
			l=mid+1;
		}
	}
	return l;
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>n>>q;
	for(int vl=1;vl<=q;vl++){
		cin>>idx>>val;
		long pos=search(1,idx,idx,val);
		long long dm=get_max(1,1,n,pos,idx);
		long long dm3=idx-pos+1;
		val-=dm*dm3-get_sum(1,1,n,pos,idx);
		update(1,1,n,pos,idx,dm);
		long long dm1=val/dm3;
		long long dm2=val%dm3;
		update(1,1,n,pos,idx,dm+dm1);
		update(1,1,n,pos,pos+dm2-1,dm+dm1+1);
	}
	for(int i=1;i<=n;i++){
		cout<<get_max(1,1,n,i,i)<<endl;
	}
}