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 ll long long
ll T[1<<18],val[1<<18];
bool tag[1<<18];
void setval(int node,int left,int right,ll x){
	tag[node]=1;
	T[node]=x*(right-left+1);
	val[node]=x;
}
void pushdown(int node,int left,int right){
	if(tag[node]){
		int mid=left+right>>1;
		setval(node<<1,left,mid,val[node]);
		setval(node<<1|1,mid+1,right,val[node]);
		tag[node]=0;
	}
}
void modify(int node,int left,int right,int l,int r,ll x){
	if(l==left&&r==right)setval(node,l,r,x);
	else{
		pushdown(node,left,right);
		int mid=left+right>>1;
		if(r<=mid)modify(node<<1,left,mid,l,r,x);
		else if(l>mid)modify(node<<1|1,mid+1,right,l,r,x);
		else{
			modify(node<<1,left,mid,l,mid,x);
			modify(node<<1|1,mid+1,right,mid+1,r,x);
		}
		T[node]=T[node<<1]+T[node<<1|1];
	}
}
ll getsum(int node,int left,int right,int l,int r){
	if(l==left&&r==right)return T[node];
	pushdown(node,left,right);
	int mid=left+right>>1;
	if(r<=mid)return getsum(node<<1,left,mid,l,r);
	if(l>mid)return getsum(node<<1|1,mid+1,right,l,r);
	return getsum(node<<1,left,mid,l,mid)+getsum(node<<1|1,mid+1,right,mid+1,r);
}
int main(){
	int N,Q,a;
	ll b;
	scanf("%d%d",&N,&Q);
	while(Q--){
		scanf("%d%lld",&a,&b);
		int left=0,right=a,mid;
		while(right-left>1){
			mid=left+right>>1;
			if(getsum(1,1,N,mid,mid)*(a-mid+1)-getsum(1,1,N,mid,a)<=b)right=mid;
			else left=mid;
		}
		ll tmp=getsum(1,1,N,right,right),tmp1,tmp2;
		b-=tmp*(a-right+1)-getsum(1,1,N,right,a);
		tmp1=b/(a-right+1);
		tmp2=b%(a-right+1);
		modify(1,1,N,right,a,tmp+tmp1);
		if(tmp2)modify(1,1,N,right,right+tmp2-1,tmp+tmp1+1);
	}
	for(int i=1;i<=N;i++)printf("%lld\n",getsum(1,1,N,i,i));
}