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