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 rep(i, a, b) for(int i = (a), i##_end_ = (b); i <= i##_end_; ++i)
#define drep(i, a, b) for(int i = (a), i##_end_ = (b); i >= i##_end_; --i)
#define clar(a, b) memset((a), (b), sizeof(a))
#define debug(...) fprintf(stderr, __VA_ARGS__)
typedef long long LL;
typedef long double LD;
LL read() {
    char ch = getchar();
    LL x = 0, flag = 1;
    for (;!isdigit(ch); ch = getchar()) if (ch == '-') flag *= -1;
    for (;isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;
    return x * flag;
}
void write(int x) {
    if (x < 0) putchar('-'), x = -x;
    if (x >= 10) write(x / 10);
    putchar(x % 10 + 48);
}

const int Maxn = 100009;
int n, q;

template <int N> struct SGMTtree {
	pair<LL, int> t[N << 3]; LL add[N << 3];
#define lc(x) ((x) << 1)
#define rc(x) ((x) << 1 | 1)
#define ls rt << 1, l, mid
#define rs rt << 1 | 1, mid + 1, r
	void pushup(int u) {
		t[u] = min(t[lc(u)], t[rc(u)]);
	}
	void pushdown(int u) {
		if (add[u]) {
			add[lc(u)] += add[u]; add[rc(u)] += add[u];
			t[lc(u)].first += add[u]; t[rc(u)].first += add[u];
			add[u] = 0;
		}
	}

	void build(int rt, int l, int r) {
		if (l == r) {
			t[rt] = make_pair(0, l);
			return ;
		}

		int mid = (l + r) >> 1;
		build(ls), build(rs);
		pushup(rt);
	}

	void modify(int rt, int l, int r, int P, int Q, LL v) {
		if (P > Q) return;
		if (P <= l && r <= Q) {
			add[rt] += v; t[rt].first += v;
			return ;
		}

		int mid = (l + r) >> 1; pushdown(rt);
		if (Q <= mid) modify(ls, P, Q, v);
		else if (P >= mid + 1) modify(rs, P, Q, v);
		else modify(ls, P, Q, v), modify(rs, P, Q, v);
		pushup(rt);
	}

	pair<LL, int> query(int rt, int l, int r, int P, int Q) {
		if (P > Q) return {-1, INT_MIN};
		if (P <= l && r <= Q) return t[rt];

		int mid = (l + r) >> 1; pushdown(rt);
		if (Q <= mid) return query(ls, P, Q);
		else if (P >= mid + 1) return query(rs, P, Q);
		else return min(query(ls, P, Q), query(rs, P, Q));
	}
#undef lc
#undef rc
#undef ls
#undef rs
}; SGMTtree <Maxn> st;

void init() {
	n = read(); q = read();
	st.build(1, 1, n);
}

int Find(LL v, int l, int r) {
	int ans = -1;
	while (l <= r) {
		int mid = (l + r) >> 1;
		if (st.query(1, 1, n, mid, mid).first <= v) l = mid + 1;
		else r = mid - 1, ans = mid;
	}
	return ans;
}

void solve() {
	rep (i, 1, q) {
		int r = read(); LL v = read();
		if (r == 1) {
			st.modify(1, 1, n, 1, 1, v);
			v = 0;
		}
		while (v) {
			pair<LL, int> k = st.query(1, 1, n, 1, r);
			int pos = Find(k.first, k.second, r);
			if (pos == -1) pos = r; else --pos;
			LL z = st.query(1, 1, n, 1, k.second - 1).first;

			if (z == -1) {
				LL rest = v % r, partly = v / r;
				st.modify(1, 1, n, 1, r, partly);
				if (rest) st.modify(1, 1, n, 1, rest, 1);
				v = 0;
			} else {
				if ((z - k.first) * (pos - k.second + 1) <= v) {
					st.modify(1, 1, n, k.second, pos, z - k.first);
					v -= (z - k.first) * (pos - k.second + 1);
				} else {
					LL rest = v % (pos - k.second + 1), partly = v / (pos - k.second + 1);
					st.modify(1, 1, n, k.second, pos, partly);
					if (rest) st.modify(1, 1, n, k.second, k.second + rest - 1, 1);
					v = 0;
				}
			}
		}	
	}

	rep (i, 1, n) 
		printf("%lld\n", st.query(1, 1, n, i, i).first);
}

int main() {
//	freopen("ATCs8pc_3_f.in", "r", stdin);
//	freopen("ATCs8pc_3_f.out", "w", stdout);

	init();
	solve();

#ifdef Qrsikno
    debug("\nRunning time: %.3lf(s)\n", clock() * 1.0 / CLOCKS_PER_SEC);
#endif
    return 0;
}