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:
#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
using namespace std;

class SegmentTree
{
private:
    int n;
    vector<long long> data;
    vector<long long> mulDelay;
    vector<long long> addDelay;
    void updateTree(int a, int b, int k, int l, int r, long long mulNum, long long addNum){
        if(a <= l && r <= b){
            data[k] *= mulNum;
            data[k] += addNum * (r - l + 1);
            mulDelay[k] *= mulNum;
            addDelay[k] *= mulNum;
            addDelay[k] += addNum;
        }
        else if(a <= r && l <= b){
            for(int i=0; i<2; ++i){
                data[k*2+1+i] *= mulDelay[k];
                data[k*2+1+i] += addDelay[k] * (r - l + 1) / 2;
                mulDelay[k*2+1+i] *= mulDelay[k];
                addDelay[k*2+1+i] *= mulDelay[k];
                addDelay[k*2+1+i] += addDelay[k];
            }
            mulDelay[k] = 1;
            addDelay[k] = 0;
            updateTree(a, b, k*2+1, l, (l+r)/2, mulNum, addNum);
            updateTree(a, b, k*2+2, (l+r+1)/2, r, mulNum, addNum);
            data[k] = data[k*2+1] + data[k*2+2];
        }
    }
    long long getValue(int a, int b, int k, int l, int r){
        long long ret = 0;
        if(a <= l && r <= b){
            return data[k];
        }else if(a <= r && l <= b){
            ret += getValue(a, b, k*2+1, l, (l+r)/2);
            ret += getValue(a, b, k*2+2, (l+r+1)/2, r);
        }
        return ret;
    }
public:
    SegmentTree(int n0){
        n = 1;
        while(n < n0)
            n *= 2;
        data.assign(2*n-1, 0);
        mulDelay.assign(2*n-1, 1);
        addDelay.assign(2*n-1, 0);
    }
    void set(int a, int b, long long x){ // 区間[a,b]の要素をxにする
        updateTree(a, b, 0, 0, n-1, 0, x);
    }
    void add(int a, int b, long long x){ // 区間[a,b]の要素にxを加算
        updateTree(a, b, 0, 0, n-1, 1, x);
    }
    void mul(int a, int b, long long x){ // 区間[a,b]の要素にxを乗算
        updateTree(a, b, 0, 0, n-1, x, 0);
    }
    long long get(int a, int b){         // 区間[a,b]の総和を返す
        updateTree(a, b, 0, 0, n-1, 1, 0);
        return getValue(a, b, 0, 0, n-1);
    }
};

int main()
{
    int n, q;
    cin >> n >> q;

    SegmentTree st(n);
    while(--q >= 0){
        int a;
        long long b;
        cin >> a >> b;
        -- a;

        int left = 0;
        int right = a;
        while(left < right){
            int x = (left + right + 1) / 2;
            int w = a - x + 1;
            long long h = st.get(x-1, x-1);
            long long add = h * w - st.get(x, a);
            if(b <= add)
                left = x;
            else
                right = x - 1;
        }

        int x = left;
        int w = a - x + 1;
        b += st.get(x, a);
        st.set(x, a, b / w);
        if(b % w != 0)
            st.add(x, x + b % w - 1, 1);
    }

    for(int i=0; i<n; ++i)
        cout << st.get(i, i) << endl;

    return 0;
}