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>

using namespace std;

#define int long long

struct Node
{
	long long lazy;
	Node(){}
}Tree[400001];

int n,q;
int arr[100001];

template <typename T>
inline void Read(T& x)
{
    bool Neg = false;
    char c;
    for (c = getchar(); c < '0' || c > '9'; c = getchar())
        if (c == '-') Neg = !Neg;
    x = c - '0';
    for (c = getchar(); c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
    if (Neg) x = -x;
}

template <typename T>
inline void Write(T x)
{
    if (x < 0)
    {
        putchar('-'); x = -x;
    }
    T p = 1;
    for (T temp = x / 10; temp > 0; temp /= 10) p *= 10;
    for (; p > 0; x %= p, p /= 10) putchar(x / p + '0');
}

void diffuse(int node,int l,int r)
{
	if (l != r)
	{
		Tree[node*2].lazy += Tree[node].lazy;
		Tree[node*2 + 1].lazy += Tree[node].lazy;
	}
	else
		arr[l] += Tree[node].lazy;
	Tree[node].lazy = 0;			
}

void update(int node,int l,int r,int ll,int rr,int val)
{
	if (r < ll || rr < l)
		return;
	if (ll <= l && r <= rr)
	{
		Tree[node].lazy += val;
		return;
	}	
	int mi = (l + r) / 2;
	update(node*2,l,mi,ll,rr,val);
	update(node*2+1,mi+1,r,ll,rr,val);
	return;
}

int query(int node,int l,int r,int x)
{
	diffuse(node,l,r);
	if (l == r && l == x)
		return arr[l];	
	int mi = (l + r) / 2;
	if (x <= mi) return query(node*2,l,mi,x);
	return query(node*2+1,mi+1,r,x);
}

int32_t main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	Read(n);
	Read(q);
	//cin >> n >> q;
	while(q--)
	{
		int r;
		int p;
		Read(r);
		Read(p);
		//cin >> r >> p;
		while(p)
		{
			int pos = r;
			int L = 1, R = r;
    		while(L <= R)
    		{
    			int mi = (L + R) / 2;
    			if (query(1,1,n,mi) == query(1,1,n,r))
    			{
    				pos = mi;
    				R = mi - 1;
    			}
    			else
    				L = mi + 1;
    		}
    		if (pos != 1)
    		{
    			int val_r = query(1,1,n,r);
    			int b = query(1,1,n,pos-1);
				int z = (r - pos + 1) * (b - val_r);
				if (p <= z)
				{
					int z = (r - pos + 1);
					int zz = p / z;
					update(1,1,n,pos,r,zz);
					p -= (zz*z);
					if (p)
						update(1,1,n,pos,pos + p - 1,1);
					p = 0; 
				}
				else
				{
					p -= z;
					update(1,1,n,pos,r,b - val_r);
				}	
			}
			else
			{
				int z = (r - pos + 1);
				int zz = p / z;
				update(1,1,n,1,r,zz);
				p -= (zz*z);
				if (p)
					update(1,1,n,1,p,1);
				p = 0;
			}	
		}
	}
	for (int i=1;i<=n;i++)
	{
		Write(query(1,1,n,i));
		putchar('\n');
		//cout << query(1,1,n,i) << ' ';
	}	
}