#include <bits/stdc++.h>
#define ll long long
#define sit set<node>::iterator
using namespace std;

struct node{
int l, r;
mutable ll val;
int operator<(const node &a) const{
return l<a.l;
}
node(int L, int R, ll Val): l(L), r(R), val(Val){}
node(int L) : l(L){}
};

struct odTree{
set<node> s;
sit Split(int pos){//一个节点分裂[l, r]->[l, pos-1]+[pos, r]
sit it=s.lower_bound(node(pos));
if(it!=s.end()&&it->l==pos) return it;
--it;
int l=it->l, r=it->r;
ll val=it->val;
s.erase(it);
s.insert(node(l, pos-1, val));
return s.insert(node(pos, r, val)).first;
}
void Assign(int l, int r, ll val){//区间赋值
sit it2=Split(r+1), it1=Split(l);
s.erase(it1, it2);
s.insert(node{l, r, val});
}
void Add(int l, int r){//区间[l, r] a[i]取反
sit it2=Split(r+1), it1=Split(l);
for(sit it=it1; it!=it2; ++it) it->val^=1;
}
ll Query(int l, int r){//求[l, r]的1的个数
sit it2=Split(r+1), it1=Split(l);
ll res=0;
for(sit it=it1; it!=it2; ++it){
if(it->val==1){
res+=((it->r)-(it->l)+1);
}
}
return res;
}
ll Query2(int l, int r){//求[l, r]的0连续1的个数
sit it2=Split(r+1), it1=Split(l);
ll res=0, tmp=0;
for(sit it=it1; it!=it2; ){
if(it->val==1){
tmp=0;
while(it!=it2&&it->val==1){
tmp+=((it->r)-(it->l)+1);
++it;
}
res=max(res, tmp);
}
else{
++it;
}
}
return res;
}

}Tree;

int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}

int main(){

int n, m, val;
for(int i=1; i<=n; i++){
Tree.s.insert(node(i, i, (ll)val));
}
Tree.s.insert(node(n+1, n+1, -1));
for(int i=1; i<=m; i++){