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;
ll INF = (1LL<<60);

struct segtree{
  vector<ll> t,u;
  int n;
   
  void init(int _n){
    n=1;
    while(n<_n)n*=2;
    t.clear();
    u.clear();
    t.resize(2*n);
    u.resize(2*n);
    for(int i=0;i<2*n;i++)t[i]=u[i]=0;
  }
   
  void delay(int k,int l,int r){
    if(r-l==1)return;
    t[k*2+1]+=u[k];
    u[k*2+1]+=u[k];
    t[k*2+2]+=u[k];
    u[k*2+2]+=u[k];
    u[k]=0;
  }
   
  void add(int a,int b,ll x,int k,int l,int r){
    if(b<=l || r<=a)return;
    delay(k,l,r);
    if(a<=l && r<=b){
      t[k]+=x;
      u[k]+=x;
    }else{
      int m=(l+r)/2;
      add(a,b,x,k*2+1,l,m);
      add(a,b,x,k*2+2,m,r);
      t[k]=min(t[k*2+1],t[k*2+2]);
    }
  }
   
  ll query(int a,int b,int k,int l,int r){
    if(b<=l || r<=a)return INF;
    delay(k,l,r);
    if(a<=l && r<=b){
      return t[k];
    }else{
      int m=(l+r)/2;
      ll lc=query(a,b,k*2+1,l,m);
      ll rc=query(a,b,k*2+2,m,r);
      return min(lc,rc);
    }
  }
   
  void add(int a,int b,ll x) {
    add(a,b,x,0,0,n);
  }
   
  ll query(int a,int b){
    return query(a,b,0,0,n);
  }
};


int N,Q;
segtree T;

void solve(ll a,ll b){
  while(b){

    //    for(int i=0;i<N;i++)cout<<T.query(i,i+1)<<' ';cout<<endl;
    
    ll key=T.query(a-1,a);
    ll left=0,right=a-1,mid;
    while(left<right){
      mid=(left+right)/2;
      if(T.query(mid,mid+1)>key)left=mid+1;
      else right=mid;
    }
    ll L=left, R=a;
    //    cout<<L<<' '<<R<<endl<<endl;
    
    if(R-L>=b){
      T.add(L,L+b,1);
      break;
    }

    ll target;
    if(L==0)target=INF;
    else target=T.query(L-1,L);

    
    ll total;
    if(target==INF)total=INF;
    else total=(R-L)*(target-key);
    
    if(b>=total){
      b-=total;
      T.add(L,R, target-key );
    }else{
      ll esc=b/(R-L);
      T.add(L,R, esc );
      b-=esc*(R-L);
    }
  }
}

int main(){
  scanf("%d %d",&N,&Q);
  T.init(N);
  
  for(int i=0;i<Q;i++){
    ll a,b;
    scanf("%lld %lld",&a,&b);
    solve(a,b);
  }
  
  for(int i=0;i<N;i++){
    ll ans=T.query(i,i+1);
    printf("%lld\n",ans);
  }
  return 0;
}