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;

typedef long long ll;

struct Node {
    ll sum, val;
};

struct IT {
private:
    vector<Node> t;
    int n;

    void propagate(int id, int l, int r) {
        ll &x = t[id].val;
        if (x != -1) {
            int m = (l+r)/2;
            t[2*id].val = t[2*id+1].val = x;
            t[2*id].sum = (m-l+1)*x;
            t[2*id+1].sum = (r-m)*x;
            x = -1;
        }
    }

    void update(int id, int l, int r, int i, int j, ll x) {
        if (l > j || r < i) return;
        if (i <= l && r <= j) {
            t[id].val = x;
            t[id].sum = (r-l+1)*x;
            return;
        }
        propagate(id, l, r);
        int m = (l+r)/2;
        update(2*id, l, m, i, j, x); update(2*id+1, m+1, r, i, j, x);
        t[id].sum = t[2*id].sum + t[2*id+1].sum;
    }

    long long query(int id, int l, int r, int i, int j) {
        if (l > j || r < i) return 0;
        if (i <= l && r <= j) return t[id].sum;
        propagate(id, l, r);
        int m = (l+r)/2;
        return query(2*id, l, m, i, j) + query(2*id+1, m+1, r, i, j);
    }

public:
    IT(int n): n(n) {t.assign(4*n+1, {0, -1});}

    void update(int i, int j, ll x) {update(1, 1, n, i, j, x);}

    long long query(int i, int j) {return query(1, 1, n, i, j);}
};

int main () {
    int n, q;
    scanf("%d%d", &n, &q);

    IT t(n);

    for(int i = 0; i < q; ++i) {
        int a; ll b;
        scanf("%d%lld", &a, &b);

        int lo = 1, hi = a-1, res = a;
        while (lo <= hi) {
            int mid = (lo + hi)/2;
            ll tMid = t.query(mid, mid);
            ll x = (a-mid+1)*tMid - t.query(mid, a);

            if (x <= b) {
                res = mid;
                hi = mid-1;
            } else
                lo = mid+1;
        }

        ll tRes = t.query(res, res);
        b -= (a-res+1) * tRes - t.query(res, a);

        ll tA = tRes + b/(a-res+1);
        int extra = b%(a-res+1);
        int lastExtra = res + extra - 1;
        t.update(res, lastExtra, tA + 1);
        t.update(lastExtra + 1, a, tA);
    }

    for(int i = 1; i <= n; ++i)
        printf("%lld\n", t.query(i, i));

    return 0;
}