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;
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define mp(a,b) make_pair((a),(b))
#define pb(a) push_back((a))
#define all(x) (x).begin(),(x).end()
#define uniq(x) sort(all(x)),(x).erase(unique(all(x)),end(x))
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

#define INF 21474836001234567L

class SegTree{
public:
  int n;
  vector<long> data, sum; // data: 区間内の値，sum:区間内の実際の和
  inline void lazy_eval(int k, int l, int r){
    if(data[k]>0){ // 最新の更新が下に伝搬していないとき
      sum[k] = data[k]*(r-l);
      if(k<n-1){
        data[2*k+1]=data[k];
        data[2*k+2]=data[k];
      }
      data[k]=0;
    }
  }
  void _update(int a, int b, long v, int k, int l, int r){
    lazy_eval(k,l,r);
    if(r<=a || b<=l) return;
    if(a<=l && r<=b){
      data[k] = v;
      lazy_eval(k,l,r);
      return;
    }
    int m=(l+r)/2;
    _update(a,b,v,k*2+1,l,m);
    _update(a,b,v,k*2+2,m,r);
    sum[k] = sum[k*2+1] + sum[k*2+2];
    return;
  }
  // [a,b) をvに更新
  void update(int a, int b, long v){ _update(a,b,v,0,0,n); }

  long _sum(int a, int b, int k, int l, int r){
    lazy_eval(k,l,r);
    if(r<=a || b<=l) return 0;
    if(a<=l && r<=b) return sum[k];
    int m=(l+r)/2;
    long vl = _sum(a,b,k*2+1,l,m);
    long vr = _sum(a,b,k*2+2,m,r);
    sum[k] = sum[k*2+1] + sum[k*2+2]; //??
    return vl+vr;
  }
  // [a,b) の合計
  long query(int a,int b){ return _sum(a,b,0,0,n); }

  SegTree(int n_){
    n=1;
    while(n<n_) n*=2;
    data = vector<long>(2*n-1, 0);
    sum = vector<long>(2*n-1, 0);
  }
};

int main(){
  int n,q;
  cin>>n>>q;
  vector<int> a(q);
  vector<long> b(q);
  rep(i,q) cin>>a[i]>>b[i];

  SegTree st(n);

  rep(i,q){
    int li=-1,ri=a[i];
    while(ri-li>1){
      int mi=(li+ri)/2;
      // [mi,a[i])を埋めなおす
      long sumnew = st.query(mi,a[i]) + b[i];
      long newh = sumnew/(a[i]-mi);
      if(sumnew%(a[i]-mi)!=0) newh++;

      if(st.query(mi,mi+1) >= newh) li = mi;
      else ri = mi;
    }
    long sumnew = st.query(ri,a[i]) + b[i];
    long newh = sumnew/(a[i]-ri);
    long rem = sumnew%(a[i]-ri);
    st.update(ri+rem, a[i], newh);
    st.update(ri, ri+rem, newh+1);

//    rep(j,n) cout << st.query(j,j+1) << endl; cout<<endl;
  }

  rep(i,n) cout << st.query(i,i+1) << endl;

  return 0;
}