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 <stdio.h>
#include <iostream>
#include <cstring>
#define lch (x<<1)
#define rch ((x<<1)|1)
typedef long long ll;
const int N=100005;
int n,m;
ll mn[N<<2],tag[N<<2];
using namespace std;

void modify(int x,ll v){tag[x]+=v,mn[x]+=v;}
void updtag(int x){if (tag[x]) modify(lch,tag[x]),modify(rch,tag[x]),tag[x]=0;}
int find(int x,int L,int R,int l,int r,ll v)
{
	if (L<R) updtag(x);
	if (L==R) return L;
	int mid=L+R>>1;
	if (mid>=r) return find(lch,L,mid,l,r,v);
	if (mn[lch]<=v) return find(lch,L,mid,l,r,v);
	return find(rch,mid+1,R,l,r,v);
}
ll query(int x,int l,int r,int p)
{
	if (l<r) updtag(x);
	if (l==r) return mn[x];
	int mid=l+r>>1;
	if (mid>=p) return query(lch,l,mid,p);
	return query(rch,mid+1,r,p);
}
void update(int x,int L,int R,int l,int r,ll v)
{
	if (L<R) updtag(x);
	if (L>=l && R<=r){modify(x,v);return;}
	if (L>r || R<l) return;
	int mid=L+R>>1;
	update(lch,L,mid,l,r,v);
	update(rch,mid+1,R,l,r,v);
	mn[x]=mn[rch];
}
void calc(int x,int l,int r)
{
	if (l<r) updtag(x);
	if (l==r){printf ("%lld\n",mn[x]);return;}
	int mid=l+r>>1;
	calc(lch,l,mid),calc(rch,mid+1,r);
}
int main()
{
	#ifdef Kay
		freopen ("s8pc_3_f.in","r",stdin);
		freopen ("s8pc_3_f.out","w",stdout);
	#endif
	scanf ("%d %d",&n,&m);
	int pos;ll tot;
	while (m--)
	{
		scanf ("%d %lld",&pos,&tot);
		while (tot)
		{
			ll val=query(1,1,n,pos);
			int las=find(1,1,n,1,pos,val);
			if (las==1)
			{
				update(1,1,n,1,pos,tot/pos),tot%=pos;
				if (tot) update(1,1,n,1,tot,1);
				break;
			}
			ll lv=query(1,1,n,las-1);
			ll add=min(lv-val,tot/(pos-las+1));
			update(1,1,n,las,pos,add),tot-=add*(pos-las+1);
			val+=add;
			if (val<lv && tot){update(1,1,n,las,las+tot-1,1);break;}
		}
	}
	calc(1,1,n);
	return 0;
}