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 + 100;

void enter()
{
    freopen("solve.inp","r",stdin);
    freopen("solve.out","w",stdout);
}
const long long oo = 1e18;
long long IT[N * 4];
long long lazy[N * 4];

void cn(int i, int L, int R) {
    if (lazy[i] == 0) return;
    IT[i] = 1LL * (R - L + 1) * lazy[i];
    if (L != R) {
        lazy[i << 1] = lazy[i];
        lazy[i << 1 | 1] = lazy[i];
    }
    lazy[i] = 0;
}
void update(int i, int L, int R, int u, int v, long long val) { ///a[u -> v] = val
    cn(i, L, R);
    if (L > v || R < u) return;
    if (L >= u && R <= v) {
        lazy[i] = val;
        cn(i, L, R);
        return;
    }
    int mid = (L + R) >> 1;
    update(i << 1, L, mid, u, v, val);
    update(i << 1 | 1, mid + 1, R, u, v, val);
    IT[i] = IT[i << 1] + IT[i << 1 | 1];
}
long long Get(int i, int L, int R, int u, int v) {
    cn(i, L, R);
    if (L > v || R < u) return 0;
    if (L >= u && R <= v) return IT[i];
    int mid = (L + R) >> 1;
    long long Left = Get(i << 1, L, mid, u, v);
    long long Right = Get(i << 1 | 1, mid + 1, R, u, v);
    return Left + Right;
}
void solve()
{
    int n, Q;
    cin >> n >> Q;
    while (Q--) {
        int r;
      	long long Pi;
        cin >> r >> Pi;
        int L = 1;
        int R = r;
        int H = r;
        while (L <= R) {
            int mid = (L + R) >> 1;
            long long KC = Get(1, 1, n, mid, r);
            long long Cao = Get(1, 1, n, mid, mid);
            if ((Cao * (r - mid + 1) - KC) <= Pi) {
                R = mid - 1;
                H = mid;
            }
            else L = mid + 1;
        }
        long long Cao = Get(1, 1, n, H, H);
        long long SL = Get(1, 1, n, H, r);
        Pi -= Cao * (r - H + 1) - SL;
        long long newH = Cao + (Pi / (r - H + 1));
        long long Thua = Pi % (r - H + 1);
        update(1, 1, n, H, r, newH);
        update(1, 1, n, H, H + Thua - 1, newH + 1);
        //cout << Get(1, 1, n, 2, 2).sum << '\n';
//        for (int i = 1; i <= n; i++) cout << Get(1, 1, n, i, i).sum << ' ';
//        cout << '\n';
    }
    for (int i = 1; i <= n; i++) cout << Get(1, 1, n, i, i) << '\n';
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr);
    //enter();
    solve();
}