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 <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <functional>
#include <cmath>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <cassert>
#define SIZE 100005
#define LINF 1000000000000000005LL

using namespace std;
typedef long long int ll;
typedef pair <int,int> P;
typedef pair <P,ll> PP;

int main()
{
	int n,q;
	scanf("%d %d",&n,&q);
	set <PP> st;
	set <PP>::iterator it;
	st.insert(PP(P(0,n-1),0));
	PP dm=PP(P(-1,-1),-1);
	for(int i=0;i<q;i++)
	{
		int a;
		ll b;
		scanf("%d %lld",&a,&b);a--;
		while(1)
		{
			it=st.lower_bound(PP(P(a+1,-1),-1));
			it--;
			PP p=*it;
			PP q=dm;
			if(it!=st.begin())
			{
				it--;
				q=*it;
				it++;
			}st.erase(it);
			if(p.first.second>a) st.insert(PP(P(a+1,p.first.second),p.second));
			p.first.second=a;
			if(q!=dm&&(q.second-p.second)*(ll) (p.first.second-p.first.first+1)<=b)
			{
				b-=(q.second-p.second)*(ll) (p.first.second-p.first.first+1);
				st.erase(q);
				st.insert(PP(P(q.first.first,p.first.second),q.second));
			}
			else
			{
				p.second+=b/(ll) (p.first.second-p.first.first+1);
				b%=(ll) (p.first.second-p.first.first+1);
				if(b>0)
				{
					st.insert(PP(P(p.first.first,p.first.first+(int) b-1),p.second+1));
					p.first.first+=(int) b;
				}st.insert(p);
				break;
			}
		}
	}
	for(it=st.begin();it!=st.end();it++)
	{
		PP p=*it;
		P s=p.first;
		for(int i=s.first;i<=s.second;i++) printf("%lld\n",p.second);
	}
	return 0;
}