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 <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <set>
#define mp  make_pair
using namespace std;

typedef long long  LL;
typedef pair <int,LL>  PIL;
typedef set <PIL>::iterator  Iter;
int n,q;
set <PIL> S;

Iter pre(Iter x){x--;  return x;}

void work()
{
	scanf("%d %d",&n,&q);
	S.insert(mp(0,1LL<<45)),S.insert(mp(1,0)),S.insert(mp(n+1,-1));
	for (int i=1,a,l; i<=q; i++)
		{
			LL b;
			scanf("%d %lld",&a,&b),a++;
			Iter x=pre(S.upper_bound(mp(a,1LL<<60))),y;
			x=(S.insert(mp(a,(*x).second))).first;
			while (b>0)
				{
					y=pre(x),l=a-(*y).first;
					if (((*pre(y)).second-(*y).second)*l>=b)
						{
							if (b%l)  S.insert(mp((*y).first+b%l,(*y).second+b/l));
							S.erase(y),y=S.insert(mp((*y).first,(*y).second+(b+l-1)/l)).first;
							if ((*pre(y)).second==(*y).second)  S.erase(y);
							b=0;
						}else  b-=((*pre(y)).second-(*y).second)*l,S.erase(y);
				}
			if ((*pre(x)).second==(*x).second)  S.erase(x);
		}
	for (Iter x=S.begin(),y; x!=S.end(); y=x,x++)
		if ((*x).first>1)
			for (int i=(*y).first; i<(*x).first; i++)
				printf("%lld\n",(*y).second);
}

int main()
{
	work();
	return 0;
}