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:
// <sushi.cpp> - Sat Mar 25 08:49:56 2017
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
template<typename T>
inline void gg(T &res){
    res=0;T fh=1;char ch=getchar();
    while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
    if(ch=='-')fh=-1,ch=getchar();
    while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
    res*=fh;
}
inline int gi(){int x;gg(x);return x;}
inline lol gl(){lol x;gg(x);return x;}
const int MAXN=100010;
const int MAXK=MAXN<<2;
const lol INF=1e18;
int n,pos[MAXN];
lol val[MAXK],lazy[MAXK],mi[MAXK];
inline void update(int x){
    val[x]=val[x<<1]+val[x<<1|1];
    mi[x]=min(mi[x<<1],mi[x<<1|1]);
}
void pushdown(int x,int l,int r){
    if(!lazy[x])return;
    int m=l+r>>1;
    val[x<<1]=(m-l+1)*lazy[x];
    val[x<<1|1]=(r-m)*lazy[x];
    mi[x<<1]=mi[x<<1|1]=lazy[x<<1]=lazy[x<<1|1]=lazy[x];
    lazy[x]=0;
}
lol getsum(int L,int R,int l=1,int r=n,int x=1){
    if(l==L&&r==R)return val[x];
    pushdown(x,l,r);
    int m=l+r>>1;lol ans=0;
    if(L<=m)ans+=getsum(L,min(R,m),l,m,x<<1);
    if(R>m)ans+=getsum(max(L,m+1),R,m+1,r,x<<1|1);
    return ans;
}
int find(int p,lol s,lol y,int l=1,int r=n,int x=1){
    if(l==r)return l;
    pushdown(x,l,r);
    int m=l+r>>1;
    if(p<=m||s-val[x<<1]+y>mi[x<<1]*(p-m))return find(p,s,y,l,m,x<<1);
    return find(p,s-val[x<<1],y,m+1,r,x<<1|1);
}
void set(int L,int R,lol v,int l=1,int r=n,int x=1){
    if(L>R)return;
    if(l==L&&r==R){
        val[x]=(r-l+1)*v;
        lazy[x]=mi[x]=v;
        return;
    }
    pushdown(x,l,r);
    int m=l+r>>1;
    if(L<=m)set(L,min(R,m),v,l,m,x<<1);
    if(R>m)set(max(L,m+1),R,v,m+1,r,x<<1|1);
    update(x);
}
void dfs(int l,int r,int x){
    if(l==r){printf("%lld\n",val[x]);return;}
    pushdown(x,l,r);
    int m=l+r>>1;
    dfs(l,m,x<<1);
    dfs(m+1,r,x<<1|1);
}
int main(){
    n=gi();int m=gi();
    while(m--){
        int x=gi();
        lol s=getsum(1,x),y=gl();
        int p=find(x,s,y);s=getsum(p,x);
        set(p,x,(y+s)/(x-p+1));
        set(p,p+(y+s)%(x-p+1)-1,(y+s)/(x-p+1)+1);
    }
    dfs(1,n,1);
    return 0;
}