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<stdio.h>
#include<iostream>
#include<algorithm>
#include<stdlib.h>
#include<string.h>
#include<queue>
#define LL long long
using namespace std;
inline LL read( )
{
  LL sum=0;char c=getchar( );bool f=0;
  while(c<'0'||c>'9') {if(c=='-') f=1;c=getchar( );}
  while(c>='0'&&c<='9') {sum=sum*10+c-'0';c=getchar( );}
  if(f) return -sum;
  return sum;
}
const int N=100005;
int n,Q;LL t[N*4],cov[N*4],add[N*4];
inline void _cov(int p,LL v,int len)
{
  t[p]=v*len;
  add[p]=0;cov[p]=v;
}
inline void _add(int p,LL v,int len)
{
  t[p]+=v*len;
  if(cov[p]==-1) add[p]+=v;
  else cov[p]+=v;
}
inline void push(int p,int l,int r)
{
  LL u;int L=p<<1,R=L|1,mid=(l+r)>>1;
  if((u=add[p])) _add(L,u,mid-l+1),_add(R,u,r-mid),add[p]=0;
  if((u=cov[p])!=-1) _cov(L,u,mid-l+1),_cov(R,u,r-mid),cov[p]=-1;
}
LL v;
inline void build(int p,int l,int r)
{
  cov[p]=-1;if(l==r) return;
  int mid=(l+r)>>1;build(p<<1,l,mid);build(p<<1|1,mid+1,r);
}
inline void ch(int p,int l,int r,int L,int R)
{
  if(l==L&&r==R) {_cov(p,v,r-l+1);return;}
  push(p,l,r);
  int mid=(l+r)>>1;
  if(R<=mid) ch(p<<1,l,mid,L,R);
  else if(L>mid) ch(p<<1|1,mid+1,r,L,R);
  else ch(p<<1,l,mid,L,mid),ch(p<<1|1,mid+1,r,mid+1,R);
  t[p]=t[p<<1]+t[p<<1|1];
}
inline void up(int p,int l,int r,int L,int R)
{
  if(l==L&&r==R) {_add(p,v,r-l+1);return;}
  push(p,l,r);
  int mid=(l+r)>>1;
  if(R<=mid) up(p<<1,l,mid,L,R);
  else if(L>mid) up(p<<1|1,mid+1,r,L,R);
  else up(p<<1,l,mid,L,mid),up(p<<1|1,mid+1,r,mid+1,R);
  t[p]=t[p<<1]+t[p<<1|1];
}
inline LL ask(int p,int l,int r,int L,int R)
{
  if(l==L&&r==R) return t[p];
  push(p,l,r);
  int mid=(l+r)>>1;
  if(R<=mid) return ask(p<<1,l,mid,L,R);
  else if(L>mid) return ask(p<<1|1,mid+1,r,L,R);
  else return ask(p<<1,l,mid,L,mid)+ask(p<<1|1,mid+1,r,mid+1,R);
}
inline void DFS(int p,int l,int r)
{
  if(l==r) {printf("%lld\n",t[p]);return;}
  push(p,l,r);
  int mid=(l+r)>>1;
  DFS(p<<1,l,mid);
  DFS(p<<1|1,mid+1,r);
}
int main( )
{
  int a,l,r,mid,L,len;LL b,t;
  n=read( );Q=read( );
  build(1,1,n);
  while(Q--)
    {
      a=read( );b=read( );
      if(a==1) {v=b;up(1,1,n,1,1);continue;} //q[0]=inf
      if(ask(1,1,n,a-1,a-1)-ask(1,1,n,a,a)>=b) {v=b;up(1,1,n,a,a);continue;}
      l=2;r=a;
      while(l<=r)
	{
	  mid=(l+r)>>1;
	  if(ask(1,1,n,mid-1,mid-1)*(a-mid+1)-ask(1,1,n,mid,a)<=b) r=mid-1;
	  else l=mid+1;
	}
      L=l-1;t=ask(1,1,n,L,L);
      //printf("%d\n",L);
      b-=t*(a-r+1)-ask(1,1,n,r,a);
      //cout<<b<<endl;
      v=t;ch(1,1,n,L+1,a);
      //DFS(1,1,n);puts("");
      len=a-L+1;
      v=b/len;
      if(v) up(1,1,n,L,a);//,printf("%d %d %lld\n",L,a,v);
      b%=len;
      if(b) v=1,up(1,1,n,L,L+b-1);//,printf("%d %lld\n",L,L+b-1);
      //DFS(1,1,n);puts("");
    }
  DFS(1,1,n);
  return 0;
}