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 <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#define debug(x) cerr << #x << " = " << x << endl;


#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 100010


/* LazyPropagationSegmentTree(Sum) */
//0-index

struct LazySeg_sum{
  typedef ll Type;
  
  struct Data{
    Type val;
    Type add;
    Type sum;
    bool valset;
    
    Type calc_sum(int l, int r){
      if(valset){
        return (val + add) * (r - l + 1);
      }else{
        return sum + add * (r - l + 1);
      }
    }

    void set_data(Type x,Type y){
      val = x;
      add = y;
      valset = true;
    }

    void add_data(Type x){
      add += x;
    }
    
    Data():val(0),add(0),sum(0),valset(false){}
    
  };

  vector<Data> data;
  int seg_size;
  
  LazySeg_sum(int n){
    for(seg_size=1; seg_size < n; seg_size*=2);
    data.assign(seg_size*2, Data());
  }

  Type set(int a, int b, Type x, int l=0, int r=-1,int k=0){
    if(r == -1) r = seg_size-1;
    
    if(a <= l && r <= b){
      data[k].set_data(x,0);
      return data[k].calc_sum(l,r);
    }

    if(r < a || b < l) return data[k].calc_sum(l,r);
    
    if(data[k].valset){
      data[k*2+1].set_data(data[k].val,data[k].add);
      data[k*2+2].set_data(data[k].val,data[k].add);
    }else{
      data[k*2+1].add_data(data[k].add);
      data[k*2+2].add_data(data[k].add);
    }
      

    data[k].add = 0;
    
    data[k].valset = false;
    
    data[k].sum = set(a,b,x,l,(l+r)/2,k*2+1) + set(a,b,x,(l+r)/2+1,r,k*2+2);

    return data[k].calc_sum(l,r);
  }

  Type add(int a, int b, Type x, int l=0, int r=-1, int k=0){
    if(r == -1) r = seg_size-1;

    if(a <= l && r <= b){
      data[k].add += x;
      return data[k].calc_sum(l,r);
    }

    if(r < a || b < l) return data[k].calc_sum(l,r);

    if(data[k].valset){
      data[k*2+1].set_data(data[k].val, data[k].add);
      data[k*2+2].set_data(data[k].val, data[k].add);
      data[k].add = 0;
      data[k].valset = false;
    }

    data[k].sum = add(a,b,x,l,(l+r)/2,k*2+1) + add(a,b,x,(l+r)/2+1,r,k*2+2);

    return data[k].calc_sum(l,r);
  }
  
  Type query(int a, int b, int l=0, int r=-1, int k = 0){
    if(r == -1) r = seg_size-1;

    if(r < a || b < l) return 0;

    if((a <= l && r <= b) || data[k].valset){
      return data[k].calc_sum(max(a,l),min(b,r));
    }

    return query(a,b,l,(l+r)/2,k*2+1) + query(a,b,(l+r)/2+1,r,k*2+2) +
           data[k].add * (min(b,r) - max(a,l) + 1);
  }
  
};


LazySeg_sum seg(100000);

int main(){
  int n,q,a;
  ll b;

  scanf("%d%d",&n,&q);

  
  for(int i=0;i<q;i++){
    scanf("%d%lld",&a,&b);
    a--;

    if(a == 0){
      seg.add(0,0,b);
      continue;
    } 
    
    int l=1,r=a,mid;
    ll u,p;
    
    while(l < r){

      mid = (l+r)/2;

      u = seg.query(mid-1,mid-1);
      
      p = seg.query(mid,a);

      if((u * (a-mid+1) - p) > b){
        l = mid+1;
      }else{
        r = mid;
      }
    }
    
    p = seg.query(l,a);
    u = seg.query(l-1,l-1);

    u = min((b + p)/(a-l+1),u);
    
    b -= u*(a-l+1) - p;
    
    seg.set(l,a,u);
    
    seg.add(l-1,a,b/(a-(l-1)+1));
    b%=(a-(l-1)+1);
    
    if(b > 0)
      seg.add(l-1,b-1+(l-1),1);
  }
  
  for(int i=0;i<n;i++){
    printf("%lld\n",seg.query(i,i));
  }
  
  return 0;
}