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;
const int maxn=100005;
long long sum1[maxn<<2];//sum of val
long long sum2[maxn<<2];//sum of tot val
long long lazy[maxn<<2];
long long totnum=-20000000000010LL;
int n;
long long Start;
void Push_down(int id)
{
    lazy[id]=0;
    lazy[id<<1]=lazy[id<<1|1]=1;
    sum1[id<<1]=sum1[id<<1|1]=0;
    sum2[id<<1]=sum2[id<<1|1]=0;
}
void Push_up(int id)
{
    sum1[id]=sum1[id<<1]+sum1[id<<1|1];
    sum2[id]=sum2[id<<1]+sum2[id<<1|1];
}
void updata(int id,int l,int r,int w,long long val)
{
    if(l==r){
        sum1[id]+=val;
        sum2[id]+=val*(n+1-l);
        lazy[id]=0;
        return;
    }
    if(lazy[id]){
        Push_down(id);
    }
    int mid=(l+r)>>1;
    if(w<=mid) updata(id<<1,l,mid,w,val);
    else updata(id<<1|1,mid+1,r,w,val);
    Push_up(id);
}
void updatalazy(int id,int l,int r,int tl,int tr)
{
    if(l==tl&&r==tr){
        lazy[id]=1;
        sum1[id]=sum2[id]=0;
        return ;
    }
    if(lazy[id]) return;
    int mid=(l+r)>>1;
    if(tr<=mid)  updatalazy(id<<1,l,mid,tl,tr);
    else if(tl>mid) updatalazy(id<<1|1,mid+1,r,tl,tr);
    else{
        updatalazy(id<<1,l,mid,tl,mid);
        updatalazy(id<<1|1,mid+1,r,mid+1,tr);
    }
    Push_up(id);
}
int Q(int id,int l,int r,int x,long long &val)
{
    //printf("%d %d %d %d %lld %d\n",id,l,r,x,val,lazy[id]);
    if(lazy[id]) return -1;
    if(r<=x){
        long long tmp=sum2[id]-sum1[id]*(n-x);
        //printf("%lld %lld %lld %lld ssss\n",tmp,val,sum2[id],sum1[id]);
        if(tmp+val>=0){
            val=tmp+val;
            return -1;
        }
        else{
            if(l==r) return l;
            int mid=(l+r)>>1;
            int tt=Q(id<<1|1,mid+1,r,x,val);
            if(tt!=-1) return tt;
            tt=Q(id<<1,l,mid,x,val);
            return tt;
        }
    }
    int mid=(l+r)>>1;
    if(x<=mid) return Q(id<<1,l,mid,x,val);
    else{
        int tt=Q(id<<1|1,mid+1,r,x,val);
        if(tt!=-1) return tt;
        return Q(id<<1,l,mid,x,val);
    }
}
long long Qsum(int id,int l,int r,int tl,int tr)
{
    if(l==tl&&r==tr){
        return sum1[id];
    }
    if(lazy[id]) return 0;
    int mid=(l+r)>>1;
    if(tr<=mid) return Qsum(id<<1,l,mid,tl,tr);
    else if(tl>mid) return Qsum(id<<1|1,mid+1,r,tl,tr);
    else return Qsum(id<<1,l,mid,tl,mid)+Qsum(id<<1|1,mid+1,r,mid+1,tr);
}
long long ans[maxn];
void get(int id,int l,int r)
{
    if(l==r){
        ans[l]=sum1[id];
        return ;
    }
    if(lazy[id]){
        return ;
    }
    int mid=(l+r)>>1;
    get(id<<1,l,mid);
    get(id<<1|1,mid+1,r);
}
void Output()
{
    memset(ans,0,sizeof(ans));
    ans[0]=-totnum;
    get(1,1,n);
//    for(int i=1;i<=n;i++)
//        printf("%lld ",ans[i]);
//    printf("\n");
    for(int i=1;i<=n;i++)
        ans[i]+=ans[i-1];
//    for(int i=1;i<=n;i++)
//        printf("%lld ",ans[i]);
//    printf("\n");
    for(int i=1;i<=n;i++)
        printf("%lld\n",ans[i]);
}
int main()
{
    int q;
    scanf("%d%d",&n,&q);
    Start=0;
    memset(lazy,0,sizeof(lazy));
    memset(sum1,0,sizeof(sum1));
    memset(sum2,0,sizeof(sum2));
    updata(1,1,n,1,totnum);
    while(q--)
    {
        int x;
        long long val;
        scanf("%d%lld",&x,&val);
        int t=Q(1,1,n,x,val);
       // printf("%d %lld\n",t,val);
        if(t<x){
            long long sum=Qsum(1,1,n,t+1,x);
            if(x+1<=n) updata(1,1,n,x+1,sum);
            updatalazy(1,1,n,t+1,x);
        }
        long long tmp=val/(x-t+1);
        val=val%(x-t+1);
        updata(1,1,n,t,tmp);
        if(x+1<=n)
            updata(1,1,n,x+1,-tmp);
        if(val){
            updata(1,1,n,t,1);
            updata(1,1,n,t+val,-1);
        }
        //Output();
    }
    Output();
    return 0;
}