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>
using namespace std;
#include<vector>
template<typename T>
struct lazysegtree{
	int n;
	vector<T>dat,lazy;
	vector<bool>lazyflag;
	lazysegtree(int n_=0)
	{
		n=1;
		while(n<n_)n<<=1;
		dat.assign(2*n-1,0);
		lazy.assign(2*n-1,0);
		lazyflag.assign(2*n-1,false);
	}
	void eval(int i,int l,int r)
	{
		if(lazyflag[i])
		{
			dat[i]=lazy[i]*(r-l);
			if(r-l>1)
			{
				lazy[2*i+1]=lazy[i];
				lazy[2*i+2]=lazy[i];
				lazyflag[2*i+1]=lazyflag[2*i+2]=true;
			}
			lazy[i]=0;
			lazyflag[i]=false;
		}
	}
	void update(int a,int b,T x,int k=0,int l=0,int r=-1)//[a,b)
	{
		if(r<0)r=n;
		eval(k,l,r);
		if(b<=l||r<=a)return;
		else if(a<=l&&r<=b)
		{
			lazy[k]=x;
			lazyflag[k]=true;
			eval(k,l,r);
		}
		else
		{
			update(a,b,x,2*k+1,l,(l+r)/2);
			update(a,b,x,2*k+2,(l+r)/2,r);
			dat[k]=dat[2*k+1]+dat[2*k+2];
		}
	}
	T query(int a,int b,int k=0,int l=0,int r=-1)//[a,b)
	{
		if(r<0)r=n;
		eval(k,l,r);
		if(b<=l||r<=a)return 0;
		else if(a<=l&&r<=b)return dat[k];
		else return query(a,b,2*k+1,l,(l+r)/2)+query(a,b,2*k+2,(l+r)/2,r);
	}
};
int N,Q;
int main()
{
	scanf("%d%d",&N,&Q);
	lazysegtree<long>P(N);
	for(;Q--;)
	{
		int a;long b;
		scanf("%d%ld",&a,&b);
		long V;
		int l=-1,r=a;
		while(r-l>1)
		{
			int m=l+r>>1;
			long L=P.query(m,m+1)-1;
			long pL=L;
			long R=m==0?2e13:P.query(m-1,m)+1;
			long S=P.query(m,a);
			while(R-L>1)
			{
				long M=L+R>>1;
				if(M*(a-m)-S>b)R=M;
				else L=M;
			}
			if(pL==L)l=m;
			else
			{
				r=m;
				V=L;
			}
		}
		b-=V*(a-r)-P.query(r,a);
		P.update(r,a,V);
		P.update(r,r+b,V+1);
	}
	for(int i=0;i<N;i++)printf("%ld\n",P.query(i,i+1));
}