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<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<queue>
#include<set>
#define md double
#define LL long long
using namespace std;
const int N=1<<20;
int gi() {
	int w=0;bool q=1;char c=getchar();
	while ((c<'0'||c>'9') && c!='-') c=getchar();
	if (c=='-') q=0,c=getchar();
	while (c>='0'&&c <= '9') w=w*10+c-'0',c=getchar();
	return q? w:-w;
}
inline LL gL() {
	LL w=0;bool q=1;char c=getchar();
	while ((c<'0'||c>'9') && c!='-') c=getchar();
	if (c=='-') q=0,c=getchar();
	while (c>='0'&&c <= '9') w=w*10+c-'0',c=getchar();
	return q? w:-w;
}
LL e[N],sum[N],tag[N],now[N];
int dep[N];
int main()
{
	int n=gi(),Q=gi(),i,k,t,ed,siz,L,R,l,r,H=1,mid;LL q,suf,to;
	for (siz=1;siz<n+2;siz=siz<<1|1) H++;
	for (dep[1]=H,i=2;i<=(siz<<1|1);i++) dep[i]=dep[i>>1]-1;
	e[siz+1]=3e13;
#define lc (k<<1)
#define rc (lc|1)
#define pushdown tag[lc]=tag[rc]=e[lc]=e[rc]=tag[k],sum[lc]=sum[rc]=tag[k]<<dep[lc],tag[k]=0
#define update e[k]=e[rc],sum[k]=sum[lc]+sum[rc]
#define modify(k,to) tag[k]=e[k]=(to),sum[k]=(to)<<dep[k]
	while (Q--) {
		L=siz+1,R=siz+(ed=gi()+1)+1;q=gL();
		for (i=H;i;i--) {
			if (tag[k=L>>i]) pushdown;
			if ((R>>i)!=k&&tag[k=R>>i]) pushdown;
		}
		for (l=L,now[r=R]=0;l^r^1;l>>=1,r>>=1) {
			if (~l&1) now[l^1]=sum[l^1],now[l>>1]=now[l]+now[l^1]; else now[l>>1]=now[l];
			if (r&1) now[r^1]=sum[r^1],now[r>>1]=now[r^1]+now[r]; else now[r>>1]=now[r];
		}
		now[l>>1]=now[l]+now[r];
		for (k=l;(k>>=1)>1;) now[k>>1]=now[k];
		suf=0;
		for (k=l>>1,l=1,r=1<<dep[k];k<=siz;) {
			if (tag[k]) pushdown;
			if (ed<=(mid=(l+r)>>1)) k<<=1,r=mid;
			else k=k<<1|(mid=(l+r)>>1,q<=e[lc]*(ed-mid)-(r<=ed?sum[rc]:now[rc])-suf?(l=mid+1,1):(suf+=r<=ed?sum[rc]:now[rc],r=mid,0));
		}
		suf+=sum[k];
		to=(q-(e[i]*(ed-l+1)-suf))/(ed-l+1);
		q-=to*(ed-l+1)-suf;t=--k;
		l=k,r=t+q+1;
		for (i=H;i;i--) {
			if (tag[k=l>>i]) pushdown;
			if ((r>>i)!=k&&tag[k=r>>i]) pushdown;
		}
		for (;l^r^1;) {
			if (~l&1) modify(l^1,to+1);
			if (r&1) modify(r^1,to+1);
			k=l>>=1;update;
			k=r>>=1;update;
		}
		while (k=(l>>=1)) update;
		l=t+q,r=siz+ed+1;
		for (i=H;i;i--) {
			if (tag[k=l>>i]) pushdown;
			if ((r>>i)!=k&&tag[k=r>>i]) pushdown;
		}
		for (;l^r^1;) {
			if (~l&1) modify(l^1,to);
			if (r&1) modify(r^1,to);
			k=l>>=1;update;
			k=r>>=1;update;
		}
		while (k=(l>>=1)) update;
	}
	for (k=1;k<=siz;k++) if (tag[k]) pushdown;
	for (k=1;k<=n;k++) printf("%lld\n",e[k+siz+1]);
	return 0;
}