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;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))

// mod
const ll MOD = 1000000007ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

// floating
typedef double Real;
const Real EPS = 1e-11;
#define EQ0(x) (abs(x)<EPS)
#define EQ(a,b) (abs(a-b)<EPS)
typedef complex<Real> P;

int main(){
  int n,q;
  scanf("%d%d",&n,&q);
  map<pii,ll> M;
  M[pii(0,n-1)] = 0;
  while(q--){
    int a;
    ll b;
    scanf("%d%lld",&a,&b);
    --a;
    auto it = M.upper_bound(pii(a,n+252521));
    it--;
    if(it->first.second != a){
      // split
      ll val = it->second;
      int beg = it->first.first;
      int end = it->first.second;
      M.erase(it);
      M[pii(beg,a)] = val;
      M[pii(a+1,end)] = val;
      it = M.find(pii(beg,a));
    }
    while(b>0){
      bool lastflag = false;
      auto bef = it;
      if(it == M.begin()){
        lastflag = true;
      }else{
        bef--;
        ll sub = bef->second - it->second;
        ll rest = sub * (it->first.second - it->first.first + 1);
        if(b>=rest){
          b -= rest;
          // join
          ll val = bef->second;
          int beg = bef->first.first;
          int end = it->first.second;
          M.erase(bef);
          M.erase(it);
          M[pii(beg,end)] = val;
          it = M.find(pii(beg,end));
        }else{
          lastflag = true;
        }
      }
      if(lastflag){
        // split
        ll aval = it->second;
        ll bval = aval;
        int beg = it->first.first;
        int end = it->first.second;
        int cnt = end-beg+1;
        ll add = b/cnt;
        aval += add;
        bval += add;
        b -= add*cnt;
        if(b==0){
          it->second = aval;
        }else{
          M.erase(it);
          aval += 1;
          int sp = beg+b-1;
          b = 0;
          M[pii(beg,sp)] = aval;
          M[pii(sp+1,end)] = bval;
          it = M.find(pii(beg,sp));
        }
        // join
        if(it != M.begin()){
          auto bef = it; bef--;
          if(bef->second == it->second){
            ll val = it->second;
            int beg = bef->first.first;
            int end = it->first.second;
            M.erase(bef);
            M.erase(it);
            M[pii(beg,end)] = val;
          }
        }
      }
    }
    // debug
    // it = M.begin();
    // REP(i,n){
    //   printf("%lld ",it->second);
    //   if(i == it->first.second){
    //     it++;
    //   }
    // }
    // putchar('\n');
  }
  auto it = M.begin();
  REP(i,n){
    printf("%lld\n",it->second);
    if(i == it->first.second){
      it++;
    }
  }
  return 0;
}