# 【模板库】Fenwick Tree RMQ version

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;

const int N = 200000+9;
const int INF = 1000000000;

int n,m;
char pat[10];

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
return ret*f;
}

namespace Fenwick_Tree{
#define BIT Fenwick_Tree
#define lowbit(x) ((x)&(-(x)))
int MX[N],arr[N];

inline void init(){
for (int i=1;i<=n;i++)
MX[i] = -INF;
}

inline void modify(int pos, int val){
int pre = arr[pos]; arr[pos] = val;
if (val >= pre) {
for (int i=pos;i<=n;i+=lowbit(i))
MX[i] = max(MX[i],val);
} else {
for (int i=pos;i<=n;i+=lowbit(i)) {
MX[i] = arr[i];
for (int j=lowbit(i)/2;j;j>>=1)
MX[i] = max(MX[i],MX[i-j]);
}
}
}

inline int query(int l, int r) {
int ret = -INF;
while (r >= l) {
if (r-lowbit(r)+1 >= l) ret = max(ret, MX[r]), r -= lowbit(r);
else ret = max(ret, arr[r]), r--;
}
return ret;
}
};

int main(){
while (~scanf("%d%d",&n,&m)) {
BIT::init();
for (int i=1,l,r;i<=m;i++) {
scanf("%s",pat+1);