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;
typedef long long ll;
const int MAX = 111111;
const ll INF = 1000000000000000000LL;

class SEG{
  int n;
  ll dat[2*(1<<18)-1];

public:
  SEG(int _n = MAX){ 
    n = 1;
    while(n < _n) n *= 2;
    fill(dat,dat+2*n-1,0);
  }

  // get k-th
  ll get(int k){
    k += n - 1;
    ll ret = dat[k];
    while(k > 0){
      k = (k - 1) / 2;
      ret += dat[k];
    }
    return ret;
  }

  // add x to [a,b) 
  void query(int a, int b,ll x ){ return query(a, b, x, 0, 0, n);}
  void query(int a, int b, ll x, int k, int l, int r){
    if(r <= a || b <= l) return;
    if(a <= l && r <= b) dat[k] += x;
    else{
      query(a, b, x, k*2+1, l, (l+r)/2);
      query(a, b, x, k*2+2, (l+r)/2, r);
    }
  }
};

SEG seg;
int N,Q;


void calc(ll a,ll b){
  //  cout << "calc : " << a << " " << b << endl;
  ll x = seg.get( a );
  int st = 0, ed = a;
  int r = a;
  while( st <= ed ){
    int h = (st+ed)/2;
    if( seg.get(h) == x ) {
      r = h;
      ed = h-1;
    } else
      st = h+1;    
  }

  ll inv = a-r+1;
  if( r == 0 ){
    seg.query( 0, a+1, b/(a+1) );
    seg.query( 0, b%(a+1), 1 );
  } else {
    ll y = seg.get( r-1 );
    if( b > (y-x) * inv ){
      seg.query( r, a+1, (y-x) );
      calc(a, b-(y-x)*inv);
    } else {
      seg.query( r, a+1, b / inv );
      seg.query( r, r + b % inv, 1 );      
    }
  }
}

int main(){
  cin >> N >> Q;
  for(int i=0;i<Q;i++){
    ll a,b; cin >> a >> b; --a;
    calc( a, b );
  }
  for(int i=0;i<N;i++){
    cout << seg.get(i) << endl;
  }
}