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 <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <set>

using namespace std;
using ll = long long;
using ull = unsigned long long;
constexpr ll TEN(int n) { return (n==0) ? 1 : 10*TEN(n-1); }

int main() {
    ios::sync_with_stdio(0);
    int n, q;
    cin >> n >> q;
    //cout << n << " " << q << endl;
    using P = pair<int, ll>;
    set<P> s;
    s.insert(P(-1, 3*TEN(13)));
    s.insert(P(n-1, 0));

    for (int i = 0; i < q; i++) {
        int a; ll b;
        cin >> a >> b; a--;
        while (b) {
            auto it = s.lower_bound(P(a, -1));
            auto pr = *it; it--;
            auto pl = *it;
            int d = a-pl.first;
            if (a == pr.first) s.erase(pr);
            if (d*(pl.second-pr.second) <= b) {
                s.erase(pl); 
                s.insert(P(a, pl.second));
                b -= d*(pl.second-pr.second);
            } else {                
                s.insert(P(a, pr.second + b/d));
                if (b%d) {
                    s.insert(P(pl.first + b%d, pr.second + b/d + 1));
                }
                if (pr.second + (b+d-1)/d == pl.second) {
                    s.erase(pl);
                }
                b = 0;
            }
        }
    }

    ll res[n];
    int b = -1;
    for (auto p: s) {
        for (int i = b+1; i <= p.first; i++) {
            res[i] = p.second;
        }
        b = p.first;
    }

    for (int i = 0; i < n; i++) {
        cout << res[i] << endl;
    }
    return 0;
}