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_update, lazy_add; vector<bool> lazyFlag;
        void eval(int k) {
            if(lazyFlag[k]){
                lazy_update[k] += lazy_add[k];
                node[k] = lazy_update[k];
                if(k < n) {
                    lazy_add[2*k] = lazy_add[2*k+1] = 0;
                    lazy_update[2*k] = lazy_update[2*k+1] = lazy_update[k];
                    lazyFlag[2*k] = lazyFlag[2*k+1] = true;
                }
                lazy_add[k] = 0, lazyFlag[k] = false;
            }else if(lazy_add[k] != 0){
                node[k] += lazy_add[k];
                if(k < n){
                    lazy_add[2*k] += lazy_add[k]; lazy_add[2*k+1] += lazy_add[k];
                }
                lazy_add[k] = 0;
            }
        }
     
    public:
        segtree(vector<T>& v) : n(1), sz((int)v.size()), h(0){
            while(n < sz) n *= 2, h++;
            node.resize(2*n, numeric_limits<T>::min());
            lazy_update.resize(2*n, 0); lazyFlag.resize(2*n, false);
            lazy_add.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 update(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_add[k] = 0; lazy_update[k] = x; lazyFlag[k] = true; eval(k);
            }else{
                update(a, b, x, 2*k, l, (l+r)/2); update(a, b, x, 2*k+1, (l+r)/2, r);
                node[k] = max(node[2*k], node[2*k+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_add[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;
}