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<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
#define inf (1ll<<30)
#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout)
using namespace std;

const int maxn=100010;
int n,Q;
struct node {int l,r;LL s,tag;}tr[maxn<<2];

void pushdown(int k) {
	int l=k<<1,r=k<<1|1;LL w=tr[k].tag;tr[k].tag=0;
	tr[l].s=(tr[l].r-tr[l].l+1)*w;tr[l].tag=w;
	tr[r].s=(tr[r].r-tr[r].l+1)*w;tr[r].tag=w;
}
void modify(int k,int s,int t,LL val) {
	int l=tr[k].l,r=tr[k].r,mid=(l+r)>>1;
	if (l==s && r==t) {tr[k].s=val*(tr[k].r-tr[k].l+1);tr[k].tag=val;return;}
	if (tr[k].tag) pushdown(k);
	if (t<=mid) modify(k<<1,s,t,val);
	else if (s>mid) modify(k<<1|1,s,t,val);
	else modify(k<<1,s,mid,val),modify(k<<1|1,mid+1,t,val);
	tr[k].s=tr[k<<1].s+tr[k<<1|1].s;
}
void build(int k,int s,int t) {
	tr[k].l=s;tr[k].r=t;
	if (s==t) return;
	int mid=(s+t)>>1;
	build(k<<1,s,mid);
	build(k<<1|1,mid+1,t);
}
LL query(int k,int s,int t) {
	int l=tr[k].l,r=tr[k].r,mid=(l+r)>>1;
	if (l==s && r==t) return tr[k].s;
	if (tr[k].tag) pushdown(k);
	if (t<=mid) return query(k<<1,s,t);
	else if (s>mid) return query(k<<1|1,s,t);
	else return query(k<<1,s,mid)+query(k<<1|1,mid+1,t);
}

int main() {
	scanf("%d%d",&n,&Q);
	build(1,1,n);
	for (int x,i=1;i<=Q;i++) {
		LL y;
		scanf("%d%lld",&x,&y);
		if (x==1) {modify(1,1,1,query(1,1,1)+y);continue;}
		if (query(1,x-1,x-1)-query(1,x,x)>=y) {modify(1,x,x,query(1,x,x)+y);continue;}
		int l=2,r=x,pos;
		while (l<=r) {
			int mid=(l+r)>>1;
			if (query(1,mid-1,mid-1)*(x-mid+1)-query(1,mid,x)<=y) r=mid-1,pos=mid;
			else l=mid+1;
		}
		LL val=query(1,pos-1,pos-1),num=x-pos+1;
		y-=val*num-query(1,pos,x);
		modify(1,pos,x,val);++num;
		if (y/num) modify(1,pos-1,x,val+y/num);
		if (y%num) modify(1,pos-1,pos-2+y%num,val+y/num+1);
	}
	for (int i=1;i<=n;i++) printf("%lld\n",query(1,i,i));
	return 0;
}