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 <set>
#include <vector>
#include <cstdio>
#include <assert.h>
using namespace std;
typedef long long ll;
inline ll read() {
    char ch = getchar(); ll x = 0;
    while(ch < '0' || ch > '9') ch = getchar();
    while(ch >= '0' && ch <= '9') x = x*10+ch-'0', ch = getchar();
    return x;
}


const ll INF = 2e13 + 5;
const int N = 1e5+5;

struct seg {
    int l, r;
    ll v;

    seg() {}
    seg(int a, int b, ll c): l(a), r(b), v(c) {}
    bool operator <(const seg &b) const {
        return l < b.l;
    }
};

set <seg> s;
set <seg>:: iterator it;
seg del[N], ins[N];

int t1, t2;
void work() {
    ll y = read(), x = read();
    it = s.upper_bound(seg(y, 0, 0)), --it;
    if(y+1 <= it->r) ins[++t1] = (seg(y+1, it->r, it->v));
    del[++t2] = (*it);

    int nl = it->l, nr = y; ll nv = it->v;
    for(--it; 1LL*(nr-nl+1)*(it->v-nv) < x && it != s.begin();) {
        x -= 1LL*(nr-nl+1)*(it->v-nv);
        del[++t2] = (*it);
        nl = it->l, nv = it->v, --it;
    }

    nv += x / (nr-nl+1);
    x  %= (nr-nl+1), nl = it->r+x+1;
    if(nl <= nr) ins[++t1] = (seg(nl, nr, nv));
    if(it->r < nl-1) ins[++t1] = (seg(it->r+1, nl-1, nv+1));

    for(int i = 1; i <= t2; ++i) s.erase(del[i]);
    for(int i = 1; i <= t1; ++i) s.insert(ins[i]);
    t1 = t2 = 0;
}


int n, q;
int main() {
    n = read(), q = read();

    s.insert(seg(0, 0, INF));
    s.insert(seg(1, n, 0));

    while(q--) work();
    for(it = s.begin(), ++it; it != s.end(); ++it)
        for(int j = it->l; j <= it->r; ++j)
            printf("%lld\n", it->v);
    return 0;
}