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 <cmath>

#include <map>

#define incID(i, l, r) for(int i = (l)    ; i <  (r); i++)
#define incII(i, l, r) for(int i = (l)    ; i <= (r); i++)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); i--)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); i--)
#define inc( i, n) incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define dec( i, n) decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)

typedef long long   signed int LL;
typedef long long unsigned int LU;

template<typename T> void swap(T &x, T &y) { T t = x; x = y; y = t; return; }
template<typename T> T abs(T x) { return (0 <= x ? x : -x); }
template<typename T> T max(T a, T b) { return (b <= a ? a : b); }
template<typename T> T min(T a, T b) { return (a <= b ? a : b); }
template<typename T> bool setmin(T &a, T b) { if(a <= b) { return false; } else { a = b; return true; } }
template<typename T> bool setmax(T &a, T b) { if(b <= a) { return false; } else { a = b; return true; } }
template<typename T> T gcd(T a, T b) { return (b == 0 ? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }

// ---- ----

int n, q, ans;
LL num[100001];
std::map<LL, LL> m; // pos, num

void ins(LL x, LL y) {
	auto result = m.insert(std::make_pair(x, y));
	if( ! result.second) {
		result.first -> second = y;
	}
}

int main() {
	scanf("%d%d", &n, &q);
	
	m.insert(std::make_pair(-1, 20000000000001LL));
	m.insert(std::make_pair(n, 0));
	inc(t, q) {
		int a;
		LL b;
		scanf("%d%lld", &a, &b);
		
		int ccc = 0;
		while(b > 0) {
			auto it2 = m.lower_bound(a - 1); 
			auto it = it2; it--;
			LL x = (it -> first);
			LL y = (it -> second);
			LL ny = (it2 -> second);
			LL d = a - 1 - x;
			LL s = d * (y - ny);
			
			if(b > s) {
				m.erase(x);
				ins(a - 1, y);
			} else {
				if(b > s - d) { m.erase(x); } ins((b - 1) % d + 1 + x, (b - 1) / d + 1 + ny);
				if(b > d && b % d != 0) { ins(a - 1, (b - 1) / d + ny); }
			}
			
			b -= s;
		}
	}
	
	auto it = m.begin();
	inc(i, n) {
		while(i > (it -> first)) { it++; }
		printf("%lld\n", it -> second);
	}
	
	return 0;
}