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<cstring>
#include<iostream>
#include<algorithm>
#include<set>
using namespace std;
const int M=(int)1e5+5;
const long long INF=(long long)1e17+7;
template<class T>void Rd(T &res){
	res=0;static char p;
	while(p=getchar(),p<'0');
	do{
		res=(res*10)+(p^48);
	}while(p=getchar(),p>='0');
}
template<class T>void Ps(T x){
	static int stk[65],sz;sz=0;
	while(x)stk[sz++]=x%10,x/=10;
	if(sz==0)stk[sz++]=0;
	while(sz--)putchar(stk[sz]^48);
}
int n,q;
struct W{
	int l,r;
	long long v;
	bool operator <(const W &a)const{
		if(r!=a.r)return r<a.r;
		if(l!=a.l)return l<a.l;
		return v<a.v;
	}
}A,B;
set<W>st;
set<W>::iterator it,it1;
int main(){
	Rd(n),Rd(q);
	long long x,y,ned;
	st.insert((W){0,0,INF});
	st.insert((W){1,n,0});
	for(int i=1;i<=q;i++){
		Rd(x),Rd(y);
		while(y){
			it=st.lower_bound((W){0,(int)x,0ll});
			A=(*it);
			st.erase(it);
			if(A.r>x)st.insert((W){(int)x+1,A.r,A.v}),A.r=x;
			it1=st.lower_bound((W){-1,A.l-1,0ll});
			B=(*it1);
			if(B.v!=INF)ned=(A.r-A.l+1)*(B.v-A.v);
			else ned=INF;
			if(ned<0)ned=INF;
			if(ned<=y){
				st.erase(it1);
				B.r=A.r;
				st.insert(B);
				y-=ned;
			}else {
				ned=A.r-A.l+1;
				if(y%ned==0){
					A.v+=y/ned;
					st.insert(A);
				}else {
					B.l=A.l,B.r=B.l+y%ned-1,B.v=A.v+y/ned+1;
					st.insert(B);
					A.l=B.r+1,A.v=B.v-1;
					st.insert(A);
				}
				y=0;
			}
		}
	}
	for(it=++st.begin(),it1=st.end();it!=it1;it++)
		for(int j=(*it).l;j<=(*it).r;j++)
			Ps((*it).v),putchar('\n');
	return 0;
}