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 <string>
#include <cmath>
#include <algorithm>
#include <utility>
#include <queue>
#include <set>
#include <map>
#include <deque>
#include <iomanip>
#include <cstdio>
#include <stack>
#include <numeric>

using namespace std;
typedef  long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
#define  MP make_pair
#define  PB push_back
#define inf 1000000007
#define mod 1000000007
#define rep(i,n) for(int i=0;i<(int)(n);++i)

template<typename T> class segtree {
private:
    int n,sz,h;
    vector<T> node, lazy;
    void eval(int k) {
        if(lazy[k]){
            node[k] += lazy[k];
            if(k < n) {
                lazy[k*2] += lazy[k], lazy[k*2+1] += lazy[k];
            }
            lazy[k] = 0;
        }
    }

public:
    segtree(vector<T>& v) : sz((int)v.size()), h(0) {
        n = 1;
        while(n < sz) n *= 2, h++;
        node.resize(2*n, numeric_limits<T>::min());
        lazy.resize(2*n, 0);
        for(int i = 0; i < sz; i++) node[i+n] = v[i];
        for(int i = n-1; i >= 1; i--) node[i] = max(node[2*i], node[2*i+1]);
    }
    void add(int a, int b, T x, int k=1, int l=0, int r=-1){
        if(r < 0) r = n;
        eval(k);
        if(b <= l || r <= a){
            return;
        }
        if(a <= l && r <= b){
            lazy[k] += x;
            eval(k);
        }else{
            add(a, b, x, 2*k, l, (l+r)/2);
            add(a, b, x, 2*k+1, (l+r)/2, r);
            node[k] = max(node[2*k], node[2*k+1]);
        }
    }
    T query(int a, int b) {
        a += n, b += n - 1;
        for(int i = h; i > 0; i--) eval(a >> i), eval(b >> i);
        b++;
        T res1 = numeric_limits<T>::min(), res2 = numeric_limits<T>::min();
        while(a < b) {
            if(a & 1) eval(a), res1 = max(res1, node[a++]);
            if(b & 1) eval(--b), res2 = max(res2, node[b]);
            a >>= 1, b >>= 1;
        }
        return max(res1, res2);
    }
    void print(){for(int i = 0; i < sz; i++) cout<<query(i,i+1)<< " ";cout<<endl;}
};

int main(){
    int n,q;
    cin >> n >> q;
    vector<ll>v(n+1);
    segtree<ll> sg(v);
    rep(zz,q){
        int a;
        ll b;
        scanf("%d %lld",&a,&b);
        while(b!=0){
            ll pp = sg.query(a-1,a);
    
            int ok = a-1;
            int ng = -1;
            while(ok-ng>1){
                int mid = (ok+ng)/2;
                if(sg.query(mid,a)==pp){
                    ok = mid;
                }else{
                    ng = mid;
                }
            }
            if(ok==0){
                sg.add(0,a,b/a);
                b-=(b/a)*a;
                if(b!=0){
                    sg.add(0,b,1);
                }
                b = 0;
            }else{
                ll qq = sg.query(ok-1,ok);
                if( (a-ok)*(qq-pp) <= b ){
                    sg.add(ok,a,qq-pp);
                    b -= (a-ok)*(qq-pp);
                }else{
                    ll dis = a-ok;
                    sg.add(ok,a,(b/dis));
                    b -= dis*(b/dis);
                    if(b!=0){
                        sg.add(ok,ok+b,1);
                    }
                    b = 0;
                }
            }
        }
    }
    rep(i,n){
        printf("%lld\n",sg.query(i,i+1));
    }
    return 0;
}