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 <cstdlib>
#include <algorithm>
#include <cmath>
#define file(s) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout);
using namespace std;
typedef long long ll;
const int MAXN = 200005;
const ll INF = 2e13;
int n, Q, L, R;
ll sum[MAXN << 2], _min[MAXN << 2], lazy[MAXN << 2];
ll crs_sum[MAXN << 2];

void build(int o, int l, int r) {
    lazy[o] = -1;
    if (l == r)
        return;
    int mid = (l + r) >> 1;
    build(o << 1, l, mid), build(o << 1 | 1, mid + 1, r);
}

void pushdown(const int &o, const int &l, const int &r) {
    int ls = o << 1, rs = ls | 1, mid = (l + r) >> 1;
    _min[ls] = _min[rs] = lazy[o];
    lazy[ls] = lazy[rs] = lazy[o];
    sum[ls] = (mid - l + 1) * lazy[o], sum[rs] = (r - mid) * lazy[o];
    lazy[o] = -1;
}

void update(const int &o, const int &ls, const int &rs) {
    _min[o] = _min[rs], sum[o] = sum[ls] + sum[rs];
}

void get_crs_sum(int o, int l, int r, const int &p) {
    if (l == r) {
        crs_sum[o] = sum[o];
        return;
    }
    if (lazy[o] != -1)
        pushdown(o, l, r);
    int ls = o << 1, rs = ls | 1, mid = (l + r) >> 1;
    if (p <= mid) {
        get_crs_sum(ls, l, mid, p);
        crs_sum[o] = crs_sum[ls];
    } else {
        get_crs_sum(rs, mid + 1, r, p);
        crs_sum[o] = sum[ls] + crs_sum[rs];
    }
}

int find(int o, int l, int r, int p, ll b, ll s) {
    if (l == r)
        return l;
    int ls = o << 1, rs = ls | 1, mid = (l + r) >> 1;
    if (lazy[o] != -1)
        pushdown(o, l, r);
    if (p <= mid)
        return find(ls, l, mid, p, b, 0);
    else if (p < r) {
        if ((p - mid) * _min[ls] - crs_sum[rs] >= b)
            return find(rs, mid + 1, r, p, b, 0);
        else
            return find(ls, l, mid, p, b, crs_sum[rs]);
    } else {
        if ((p - mid) * _min[ls] - (s + sum[rs]) >= b)
            return find(rs, mid + 1, r, p, b, s);
        else
            return find(ls, l, mid, p, b, s + sum[rs]);
    }
}

ll query_sum(int o, int l, int r) {
    if (L <= l && r <= R)
        return sum[o];
    if (lazy[o] != -1)
        pushdown(o, l, r);
    ll res = 0; int mid = (l + r) >> 1;
    if (L <= mid)
        res += query_sum(o << 1, l, mid);
    if (R > mid)
        res += query_sum(o << 1 | 1, mid + 1, r);
    return res;
}

void modify(int o, int l, int r, ll v) {
    if (L <= l && r <= R) {
        sum[o] = (r - l + 1) * v, _min[o] = lazy[o] = v;
        return;
    }
    if (lazy[o] != -1)
        pushdown(o, l, r);
    int ls = o << 1, rs = ls | 1, mid = (l + r) >> 1;
    if (L <= mid)
        modify(ls, l, mid, v);
    if (R > mid)
        modify(rs, mid + 1, r, v);
    update(o, ls, rs);
}

void get_element(int o, int l, int r) {
    if (l == r) {
        printf("%lld\n", _min[o]);
        return;
    }
    int ls = o << 1, rs = ls | 1, mid = (l + r) >> 1;
    if (lazy[o] != -1)
        pushdown(o, l, r);
    get_element(ls, l, mid), get_element(rs, mid + 1, r);
}

int main() {
    scanf("%d %d", &n, &Q);
    build(1, 1, n);
    int a, p; ll b, s, l, r, mid;
    for (int t = 1; t <= Q; t++) {
        scanf("%d %lld", &a, &b);
        get_crs_sum(1, 1, n, a);
        L = p = find(1, 1, n, a, b, 0), R = a;
        s = query_sum(1, 1, n);
        l = 0, r = INF;
        while (l <= r)
            (mid = (l + r) >> 1) * (R - L + 1) - s <= b ? l = mid + 1 : r = mid - 1;
        modify(1, 1, n, r);
        b = b - (R - L + 1) * r + s;
        if (L <= (R = L + b - 1))
            modify(1, 1, n, r + 1);
    }
    get_element(1, 1, n);
    return 0;
}