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>
#define N 100006
using namespace std;
long long n,m,x,y,s[4*N],f[4*N];
inline long long read()
{
	long long x=0,c=getchar();while(c<48)c=getchar();
	while(c>47)x=x*10+c-48,c=getchar();return x;
}
inline void down(long long i,long long l,long long r)
{
	if(f[i]){
		if(l!=r)f[i<<1]=f[i<<1|1]=f[i];
		s[i]=f[i]*(r-l+1);f[i]=0;
	}
}
void cover(long long i,long long l,long long r,long long x,long long y,long long p)
{
	if(x>y)return;down(i,l,r);
	if(x<=l&&r<=y){f[i]=p;return;}
	long long mid=(l+r)>>1;
	if(x<=mid)cover(i<<1,l,mid,x,y,p);
	if(y>mid)cover(i<<1|1,mid+1,r,x,y,p);
	down(i<<1,l,mid);down(i<<1|1,mid+1,r);
	s[i]=s[i<<1]+s[i<<1|1];
}
long long query(long long i,long long l,long long r,long long x,long long y)
{
	down(i,l,r);
	if(x<=l&&r<=y)return s[i];
	long long mid=(l+r)>>1,tmp=0;
	if(x<=mid)tmp=query(i<<1,l,mid,x,y);
	if(y>mid)tmp+=query(i<<1|1,mid+1,r,x,y);
	return tmp; 
}
inline long long find()
{
	long long l=1,r=x,ans;
	while(l<=r){
		long long mid=(l+r)>>1;
		if(query(1,1,n,mid,mid)*(x-mid+1)-query(1,1,n,mid,x)<=y)r=mid-1,ans=mid;
		else l=mid+1;
	}
	y-=(query(1,1,n,ans,ans)*(x-ans+1)-query(1,1,n,ans,x));
	return ans;
}
int main()
{
	n=read();m=read();
	while(m--){
		x=read();y=read();
		long long lmax=find(),cs=y/(x-lmax+1),res=y%(x-lmax+1);
		long long t=query(1,1,n,lmax,lmax);
		cover(1,1,n,lmax,lmax+res-1,t+cs+1);
		cover(1,1,n,lmax+res,x,t+cs);
	}
	for(long long i=1;i<=n;i++)printf("%lld\n",query(1,1,n,i,i));
}