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;

const int N = 1e5 + 10;

typedef long long LL;

#define lson o<<1
#define rson o<<1|1
#define gmid l[o] + r[o] >> 1

int n, Q;

LL S[N<<2], lazy[N<<2];
int l[N<<2], r[N<<2];

void build(int o, int ll, int rr){
    l[o] = ll;
    r[o] = rr;
    S[o] = lazy[o] = 0;
    if(ll < rr){
        int mid = gmid;
        build(lson, ll, mid);
        build(rson, mid+1, rr);
    }
}

void update(int o, int ll, int rr, LL v);

int pushdown(int o){
    int mid = gmid;
    if(lazy[o]){
        update(lson, l[o], mid, lazy[o]);
        update(rson, mid+1, r[o], lazy[o]);
        lazy[o] = 0;
    }
    return mid;
}

void update(int o, int ll, int rr, LL v){
    if(l[o]==ll && r[o]==rr){
        S[o] = v * (rr - ll + 1);
        lazy[o] = v;
        return;
    }
    int mid = pushdown(o);
    if(rr <= mid)   update(lson, ll, rr, v);
    else if(ll > mid)   update(rson, ll, rr, v);
    else{
        update(lson, ll, mid, v);
        update(rson, mid+1, rr, v);
    }
    S[o] = S[lson] + S[rson];
}

LL query(int o, int ll, int rr){
    if(l[o]==ll && r[o]==rr){
        return S[o];
    }
    int mid = pushdown(o);
    if(rr <= mid)   return query(lson, ll, rr);
    if(ll > mid)    return query(rson, ll, rr);
    return query(lson, ll, mid) + query(rson, mid+1, rr);
}

void solve(int a, LL b){
    int low = 1, top = a, mid, key = top;
    LL tmp, v;
    while(low <= top){
        mid = low + top >> 1;
        tmp = query(1, mid, a);
        v = query(1, mid, mid);
        if(v * (a - mid + 1) - tmp <= b){
            key = min(key, mid);
            top = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    tmp = query(1, key, a);
    v = query(1, key, key);
    int len = a - key + 1;
    LL d = v * len - tmp;
    b = b - d;
    LL g = b / len + v;
    LL h = b % len;
    if(h > 0){
        int p = key + (int)h - 1;
        update(1, key, p, g + 1);
        update(1, p+1, a, g);
    } else {
        update(1, key, a, g);
    }
}

int main(){
    while(~scanf("%d %d", &n, &Q)){
        build(1, 1, n);
        int a;
        LL b;
        for(int i=1; i<=Q; i++){
            scanf("%d %lld", &a, &b);
            solve(a, b);
        }
        for(int i=1; i<=n; i++){
            printf("%lld\n", query(1, i, i));
        }
    }
    return 0;
}