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>
#include<iostream>
#include<algorithm>

using namespace std;

typedef long long ll;
const ll INF=1e14;
const int maxn=100000+5;

int N,Q;

#define lc (x<<1)
#define rc (x<<1|1)
#define mid ((l+r)>>1)

#define val first
#define pos second
typedef pair<ll,int> Min;//Min(val,pos)

Min mn[maxn<<2];
ll add[maxn<<2];

void put_up(int x) {
	mn[x]=min(mn[lc],mn[rc]);
}

void put_down(int x) {
	if(!add[x]) return ;
	add[lc]+=add[x];
	mn[lc].val+=add[x];
	add[rc]+=add[x];
	mn[rc].val+=add[x];
	add[x]=0;
}

void build(int x,int l,int r) {
	mn[x]=Min(0,l);
	if(l==r) return ;
	build(lc,l,mid);
	build(rc,mid+1,r);
	put_up(x);
}

void update(int x,int l,int r,int ql,int qr,ll v) {
	if(ql<=l&&r<=qr) {
		add[x]+=v;
		mn[x].val+=v;
		return ;
	}
	put_down(x);
	if(ql<=mid) update(lc,l,mid,ql,qr,v);
	if(qr>mid) update(rc,mid+1,r,ql,qr,v);
	put_up(x);
}

Min query(int x,int l,int r,int ql,int qr) {
	if(ql<=l&&r<=qr) return mn[x];
	put_down(x);
	Min L(INF,N+1),R(INF,N+1);
	if(ql<=mid) L=query(lc,l,mid,ql,qr);
	if(qr>mid) R=query(rc,mid+1,r,ql,qr);
	return min(L,R);
}

int main() {
	int a;ll b;
	scanf("%d%d",&N,&Q);
	build(1,1,N);
	while(Q--) {
		scanf("%d%lld",&a,&b);
		while(b) {
			Min x=query(1,1,N,1,a);
			if(x.pos==1) {
				ll c=b/a;
				update(1,1,N,1,a,c);
				if((b-=c*a)>0) update(1,1,N,1,b,1);
				break;
			} else {
				ll v=query(1,1,N,x.pos-1,x.pos-1).val;
				if((v-x.val)*(a-x.pos+1)>b) {
					ll c=b/(a-x.pos+1);
					update(1,1,N,x.pos,a,c);
					if((b-=c*(a-x.pos+1))>0) update(1,1,N,x.pos,x.pos+b-1,1);
					break;
				} else {
					b-=(v-x.val)*(a-x.pos+1);
					update(1,1,N,x.pos,a,v-x.val);
				}
			}
		}
	}
	for(int i=1;i<=N;i++) printf("%lld\n",query(1,1,N,i,i).val);
	return 0;
}