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;
#pragma GCC optimize("Ofast")
template <typename T>
inline void read(T &x) {
	x = 0;
	bool sign = false;
	char ch = getchar();
	while (ch < '0' || '9' < ch) {
		sign |= ch == '-';
		ch = getchar();
	}
	while ('0' <= ch && ch <='9') {
		x = (x << 3) + (x << 1) + (ch ^ 48);
		ch = getchar();
	}
	x = sign ? -x : x;
}
template <typename T>
inline void print(T x) {
	static char outp[128];
	int tot = 0;
	if (!x) {
		putchar('0');
		return;
	} else if (x < 0) {
		x = -x;
		putchar('-');
	}
	while (x) { outp[tot++] = x % 10, x /= 10; }
	while (tot) { putchar(outp[--tot] + 48); }
}
typedef long long lint;
typedef unsigned int uint;
typedef pair<int, int> pii;
typedef pair<lint, lint> pll;
typedef unsigned long long ulint;
#define endl '\n'
#define fst first
#define sed second
#define pb push_back
#define mp make_pair
#define rint register int
#define newline putchar('\n')
#define leave_space putchar(' ')
#define all(x) (x).begin(), (x).end()
#define reveal(x) cerr << #x << " = " << (x) << endl
#define rep(it, f, e) for (rint it = (f); it <= (e); ++it)
#define per(it, f, e) for (rint it = (f); it >= (e); --it)
const int MAXN = 1e5 + 10;
const lint INF = 2e13 + 10;
const int MAXV = (1 << 18) + 10;
struct Segment_tree {
	#define lson (root << 1)
	#define rson (root << 1 | 1)
	#define mid ((tree[root].stdl + tree[root].stdr) >> 1)
	struct Node {
		int stdl, stdr;
		lint cover, tot;
		Node() : stdl(0), stdr(0), cover(-1), tot(0) {}
	}	tree[MAXV << 1];
	inline void buildtree(int root, int l, int r) {
		tree[root].stdl = l;
		tree[root].stdr = r;
		if (l == r) return;
		buildtree(lson, l, mid);
		buildtree(rson, mid + 1, r);
	}
	inline void update(int root) {
		if (~tree[root].cover) {
			tree[root].tot = (tree[root].stdr - tree[root].stdl + 1) * tree[root].cover;
		} else {
			tree[root].tot = tree[lson].tot + tree[rson].tot;
		}
	}
	inline void pushdown(int root) {
		if (~tree[root].cover) {
			tree[lson].cover = tree[rson].cover = tree[root].cover;
			tree[root].cover = -1;
			update(lson), update(rson);
		}
	}
	inline void cover(int root, int l, int r, lint c) {
		if (l <= tree[root].stdl && tree[root].stdr <= r) {
			tree[root].cover = c;
			update(root);
			return;
		}
		pushdown(root);
		if (l <= mid) cover(lson, l, r, c);
		if (r > mid) cover(rson, l, r, c);
		update(root);
	}
	inline lint query(int root, int l, int r) {
		if (l <= tree[root].stdl && tree[root].stdr <= r) {
			update(root);
			return tree[root].tot;
		}
		lint ret = 0;
		pushdown(root);
		if (l <= mid) ret += query(lson, l, r);
		if (r > mid) ret += query(rson, l, r);
		return ret;
	}
	#undef lson
	#undef rson
	#undef mid
}	Tree;
int main() {
	int n, q;
	read(n);
	read(q);
	Tree.buildtree(1, 0, n);
	Tree.cover(1, 0, 0, INF);
	lint a, b;
	while (q--) {
		read(a);
		read(b);
		int l = 0, r = a;
		while (l < r) {
			int mid = (l + r) >> 1;
			if (mid == a) for(;;);
			lint L = Tree.query(1, mid, mid) * (a - mid);
			lint R = Tree.query(1, mid + 1, a) + b;
			if (L <= R) r = mid;
			else l = mid + 1;
		}
		if (r == a) {
			Tree.cover(1, a, a, Tree.query(1, a, a) + b);
		} else {
			lint M = Tree.query(1, r, r);
			lint L = M * (a - r);
			lint R = Tree.query(1, r + 1, a);
			b -= L - R;
			Tree.cover(1, r + 1, a, M);
			if (a - r + 1 == 0) for(;;);
			Tree.cover(1, r, a, M + b / (a - r + 1));
			lint c = b - b / (a - r + 1) * (a - r + 1);
			if (c) Tree.cover(1, r, r + c - 1, M + b / (a - r + 1) + 1);
		}
	}
	rep (i, 1, n) {
		print(Tree.query(1, i, i));
		newline;
	}
	return 0;
}