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;

using ll = long long;

template<class T> ostream &operator <<(ostream &os, const vector<T> &v) {
    for (T x : v) os << x << " ";
    return os;
}

vector<ll> restore(multiset<pair<int, ll>> st) {
    vector<ll> ans;
    int pre = 0;
    for (auto kv : st) {
        for (int i = 0; i < kv.first - pre; i++) {
            ans.push_back(kv.second);
        }
        pre = kv.first;
    }
    return ans;
}

int main() {
    int n, q;
    cin >> n >> q;

    multiset<pair<int, ll>> st; // sum, val
    const ll inf = ll(2e13) + 100;
    st.emplace(0, inf);
    st.emplace(n, 0);

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

        while (b > 0) {
            auto cur = st.lower_bound(make_pair(a, -1));
            auto pre = prev(cur);

            int pre_sum = pre->first;
            int cnt = cur->first - pre->first;
            int front = a - pre->first;
            int back = cnt - front;
            ll val = cur->second;
            ll pre_val = pre->second;

            st.erase(cur);
            st.erase(pre);
            
            if (val + (b + front - 1) / front <= pre_val) {
                ll val0 = val + (b + front - 1) / front;
                ll val1 = val0 - 1;
                int cnt0 = b % front == 0 ? front : b % front;
                int cnt1 = front - cnt0;
                if (val0 < pre_val) {
                    st.emplace(pre_sum, pre_val);
                    if (cnt0 > 0) {
                        st.emplace(pre_sum + cnt0, val0);
                    }
                    if (cnt1 > 0) {
                        st.emplace(pre_sum + cnt0 + cnt1, val1);
                    }
                } else {
                    if (cnt0 > 0) st.emplace(pre_sum + cnt0, pre_val);
                    if (cnt1 > 0) st.emplace(pre_sum + cnt0 + cnt1, val1);
                }
                if (back > 0) st.emplace(pre_sum + cnt0 + cnt1 + back, val);
                b = 0;
            } else {
                b -= (pre_val - val) * front;
                if (front > 0) st.emplace(pre_sum + front, pre_val);
                if (back > 0) st.emplace(pre_sum + front + back, val);
            }
        }
    }

    auto ans = restore(st);
    for (int i = 0; i < ans.size(); i++) {
        printf("%lld\n", ans[i]);
    }
}