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>
#define IL inline
#define lt p<<1
#define rt p<<1|1
#define N 100003
#define REP(a,b,c) for(a=b;a<=c;a++)
using namespace std;
typedef long long lol;
const lol inf=(~0ULL)>>1;
int n,q;
int t[N<<2];
lol tag[N<<2],h[N<<2];
IL int rd(){
	int res=0;char c;while((c=getchar())<'0'||c>'9');
	while(c>='0'&&c<='9')res=res*10+c-'0',c=getchar();return res;
}
IL lol rl(){
	lol res=0;char c;while((c=getchar())<'0'||c>'9');
	while(c>='0'&&c<='9')res=res*10+c-'0',c=getchar();return res;
}
IL void build(int p,int l,int r){
	t[p]=l;if(l==r)return;int mid=(l+r)>>1;
	build(lt,l,mid),build(rt,mid+1,r);
}
IL void pushdown(int p){
	if(tag[p])h[lt]+=tag[p],h[rt]+=tag[p],tag[lt]+=tag[p],tag[rt]+=tag[p],tag[p]=0;
}
IL void output(int p,int l,int r){
	if(l==r){printf("%lld\n",h[p]);return;}
	int mid=(l+r)>>1;pushdown(p);output(lt,l,mid),output(rt,mid+1,r);
}
int mix;lol mih;
IL void query(int p,int l,int r,int x){
	int mid;mix=0,mih=inf;
	if(!x)return;
	while(l!=r){
		if(t[p]<=x){if(h[p]<mih)mix=t[p],mih=h[p];return;}
		pushdown(p);mid=(l+r)>>1;
		(x<=mid)?(r=mid,p=lt):(h[lt]<mih?(mix=t[lt],mih=h[lt]):0,l=mid+1,p=rt);
	}
	if(h[p]<mih)mix=l,mih=h[p];
}
IL void add(int p,int l,int r,int L,int R,lol v){
	if(L<=l && R>=r){h[p]+=v,tag[p]+=v;return;}
	pushdown(p);int mid=(l+r)>>1;
	if(L<=mid)add(lt,l,mid,L,R,v);if(R>mid)add(rt,mid+1,r,L,R,v);
	h[lt]<=h[rt]?(t[p]=t[lt],h[p]=h[lt]):(t[p]=t[rt],h[p]=h[rt]);
}
int main(){
  n=rd(),q=rd();int i,x,xx;lol y,hh,dt;
	build(1,1,n);
  REP(i,1,q){
		x=rd(),y=rl();
		query(1,1,n,x);
		xx=mix,hh=mih;
		while(y){
			dt=y/(x-xx+1);
			query(1,1,n,xx-1);
			if(dt>=mih-hh){
				dt=mih-hh;add(1,1,n,xx,x,dt);y-=dt*(x-xx+1);
				xx=mix,hh=mih;
			}
			else{
				add(1,1,n,xx,x,dt);y-=dt*(x-xx+1);
				if(y)add(1,1,n,xx,xx+y-1,1),y=0;
			}
		}
	}
	output(1,1,n);
  return 0;
}