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<stdio.h>
#include<algorithm>
using namespace std;
typedef long long ll;
ll mx[400010],mn[400010],s[400010],t[400010];
void pushup(int x){
	mx[x]=max(mx[x<<1],mx[x<<1|1]);
	mn[x]=min(mn[x<<1],mn[x<<1|1]);
	s[x]=s[x<<1]+s[x<<1|1];
}
void gao(int x,int len,ll v){
	mx[x]=mn[x]=v;
	s[x]=len*v;
	t[x]=v;
}
void pushdown(int x,int ln,int rn){
	if(t[x]){
		gao(x<<1,ln,t[x]);
		gao(x<<1|1,rn,t[x]);
		t[x]=0;
	}
}
void modify(int L,int R,ll v,int l,int r,int x){
	if(L<=l&&r<=R)return gao(x,r-l+1,v);
	int mid=(l+r)>>1;
	pushdown(x,mid-l+1,r-mid);
	if(L<=mid)modify(L,R,v,l,mid,x<<1);
	if(mid<R)modify(L,R,v,mid+1,r,x<<1|1);
	pushup(x);
}
ll query(int L,int R,int l,int r,int x){
	if(L<=l&&r<=R)return s[x];
	int mid=(l+r)>>1;
	ll s=0;
	pushdown(x,mid-l+1,r-mid);
	if(L<=mid)s+=query(L,R,l,mid,x<<1);
	if(mid<R)s+=query(L,R,mid+1,r,x<<1|1);
	return s;
}
int query(ll v,int l,int r,int x){
	if(l==r)return l;
	int mid=(l+r)>>1;
	pushdown(x,mid-l+1,r-mid);
	if(mn[x<<1]<=v)return query(v,l,mid,x<<1);
	return query(v,mid+1,r,x<<1|1);
}
void dfs(int l,int r,int x){
	if(l==r){
		printf("%lld\n",s[x]);
		return;
	}
	int mid=(l+r)>>1;
	pushdown(x,mid-l+1,r-mid);
	dfs(l,mid,x<<1);
	dfs(mid+1,r,x<<1|1);
}
int main(){
	int n,m,x,p;
	ll y,l,r,mid,ans,t;
	scanf("%d%d",&n,&m);
	while(m--){
		scanf("%d%lld",&x,&y);
		l=query(x,x,1,n,1);
		r=query(1,1,1,n,1)+y;
		while(l<=r){
			mid=(l+r)>>1;
			p=query(mid,1,n,1);
			t=(x-p+1)*mid-query(p,x,1,n,1);
			if(t<=y){
				ans=mid;
				l=mid+1;
			}else
				r=mid-1;
		}
		p=query(ans,1,n,1);
		y-=(x-p+1)*ans-query(p,x,1,n,1);
		modify(p,x,ans,1,n,1);
		if(y)modify(p,p+y-1,ans+1,1,n,1);
	}
	dfs(1,n,1);
}