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<bits/stdc++.h>
#include<set>
#define LL long long
#define PAIR pair<int,LL>
using namespace std;
int n,q;
set<PAIR> S;
set<PAIR> :: iterator it,ot;
int main()
{
	int x,u; LL y,v,w,s,xyk;
	scanf("%d %d",&n,&q);
	S.insert(PAIR(0,(LL)(1e18)));
	S.insert(PAIR(1,0));
	S.insert(PAIR(n+1,0));
	while(q--){
		scanf("%d %lld",&x,&y);
		it=S.upper_bound(PAIR(x+1,-1));
		it--,xyk=it->second;
		while(1){
			it=S.upper_bound(PAIR(x+1,-1));
			it--,ot=it,ot--;
			w=ot->second-it->second;
			s=x-it->first+1;
			if(y/s<w){
				u=it->first,v=it->second;
				S.erase(it);
				if(y%s==0)
					S.insert(PAIR(u,v+y/s));
				else{
					S.insert(PAIR(u,v+y/s+1));
					S.insert(PAIR(u+y%s,v+y/s));
					it=S.find(PAIR(u,v+y/s+1));
					ot=it,ot--;
					if(ot->second==v+y/s+1)
						S.erase(it);
				  }
				break;
			  }
			y-=w*s;
			S.erase(it);
		  }
		if(x<n){
			it=S.upper_bound(PAIR(x+1,-1));
			ot=it,it--;
			if(it->second>xyk&&ot->first>x+1)
				S.insert(PAIR(x+1,xyk));
		  }
	  }
	it=S.begin(),it++,x=1;
	for(;it!=S.end();it++){
		for(u=x;u<it->first;u++)
			printf("%lld\n",y);
		x=it->first,y=it->second;
	  }
	return 0;
}