一个非常重要的观察：

$$\sqrt{1 + x^2} < \sqrt{(1+x)^2}$$

也就是，对于一个点，我们一定会找一个距离最近的有点的行最远的位置，如果有多个，就找是否存在一个位置最近的有点的行只有一边有点，且这里可以和这一行错开，这样可以让距离变大一些。所以，两个点实际上的距离可以变成以行号差做第一关键字，列号差做第二关键字的距离。虽然大致思路是这样，但是其实这个东西有很多细节，如果用 set 维护会显得非常难写，于是考虑线段树维护。

我们对每一个线段树的节点维护出这个节点所代表的区间内的位置，表示用这个位置到左右最近的有点的行的距离为第一个关键字，是否可以错开作为第二关键字的大小的最大的位置，同时维护这个距离。如果区间内一个点也没有或者只有一个点，那么就不维护这两个东西了，直接设 $0$ 。

然后还需要维护最左边和最右边有点的行是谁，以及这行内有一个点（包括位置）还是两个点。

然后 pushup 是一个非常码的东西。

首先最左边和最右边点的维护是很显然的。否则，我们可以先尝试继承一下左右的最大距离。

然后考虑跨中点的情况，这个东西很需要画图推一下。大致思路是先分类讨论一下两边都是两列都有点，还是只有一边两列的有点，还是都不是两列都有点，再讨论一下长度的奇偶就行了。大致情况长这样：

然后，还需要特殊讨论一下放在开头结尾的情况。就拿线段树中开头结尾的点出来判一下即可。

用来练习代码能力算是一个好题。然后我写这题 pushup 也是重构了一次的

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 1000006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
int n , m;

pii len[MAXN << 2] , ps[MAXN << 2] , lf[MAXN << 2] , rg[MAXN << 2];
// len : the maximum distance between two person, 1 if there is only one person. second: if it not at the same line
void pu( int rt ) {
	len[rt] = ps[rt] = lf[rt] = rg[rt] = mp( 0 , 0 );
	if( !lf[rt << 1].fi && !rg[rt << 1 | 1].fi ) return;
	if( lf[rt << 1].fi ) lf[rt] = lf[rt << 1]; else lf[rt] = lf[rt << 1 | 1];
	if( rg[rt << 1 | 1].fi ) rg[rt] = rg[rt << 1 | 1]; else rg[rt] = rg[rt << 1];
	if( rg[rt << 1].fi && lf[rt << 1 | 1].fi ) {
		pii L = rg[rt << 1] , R = lf[rt << 1 | 1];
		if( L.se == 3 && R.se == 3 ) {
			len[rt] = mp( ( R.fi - L.fi ) / 2 , 0 );
			ps[rt] = mp( ( R.fi + L.fi ) / 2 , 1 );
		} else if( L.se == 3 ) {
			len[rt] = mp( ( R.fi - L.fi ) / 2 , ( R.fi + L.fi ) & 1 );
			ps[rt] = mp( ( R.fi + L.fi ) / 2 + ( ( R.fi + L.fi ) & 1 ) , ( ( R.fi + L.fi ) & 1 ) ? ( R.se ^ 3 ) : 1 );
		} else if( R.se == 3 ) {
			len[rt] = mp( ( R.fi - L.fi ) / 2 , ( R.fi + L.fi ) & 1 );
			ps[rt] = mp( ( R.fi + L.fi ) / 2 , ( ( R.fi + L.fi ) & 1 ) ? ( L.se ^ 3 ) : 1 );
		} else {
			len[rt] = mp( ( R.fi - L.fi ) / 2 , ( ( R.fi + L.fi ) & 1 ) || ( R.se == L.se ) );
			ps[rt] = mp( ( R.fi + L.fi ) / 2 , ( R.fi + L.fi & 1 || R.se == L.se ) ? ( L.se ^ 3 ) : 1 );
		}
	}
	if( len[rt << 1] >= len[rt] ) len[rt] = len[rt << 1] , ps[rt] = ps[rt << 1];
	if( len[rt << 1 | 1] > len[rt] ) len[rt] = len[rt << 1 | 1] , ps[rt] = ps[rt << 1 | 1];
}
void ins( int rt , int l , int r , pii p ) {
	if( l == r ) {
		if( lf[rt].fi ) lf[rt].se = rg[rt].se = 3 , len[rt] = mp( 0 , 0 ) , ps[rt] = mp( 0 , 0 );
		else lf[rt] = rg[rt] = p , len[rt] = mp( 1 , 0 ) , ps[rt] = mp( l , p.se ^ 3 );
		return;
	}
	int m = l + r >> 1;
	if( p.fi <= m ) ins( rt << 1 , l , m , p );
	else ins( rt << 1 | 1 , m + 1 , r , p );
	pu( rt );
}
void era( int rt , int l , int r , pii p ) {
	if( l == r ) {
		if( lf[rt].se == p.se ) lf[rt] = rg[rt] = len[rt] = ps[rt] = mp( 0 , 0 );
		else {
//			assert( ( lf[rt].se & p.se ) == p.se );
			lf[rt].se -= p.se;
			rg[rt].se = lf[rt].se;
			ps[rt] = mp( l , lf[rt].se ^ 3 ) , len[rt] = mp( 1 , 0 );
		}
		return;
	}
	int m = l + r >> 1;
	if( p.fi <= m ) era( rt << 1 , l , m , p );
	else era( rt << 1 | 1 , m + 1 , r , p );
	pu( rt );
}

pii lsj[MAXN];

void solve() {
	cin >> n >> m;
	char op[4]; int w;
	rep( i , 1 , m ) {
		scanf("%s",op);
		if( op[0] == 'E' ) {
			if( !lf[1].fi ) printf("%d %d\n",1,1) , lsj[i] = mp( 1 , 1 ) , ins( 1 , 1 , n , mp( 1 , 1 ) );
			else {
				pii le = len[1] , pp = ps[1] , tf = lf[1] , tr = rg[1];
				if( mp( tf.fi - 1 , (int)( tf.se != 3 ) ) >= le ) pp = mp( 1 , tf.se == 3 ? 1 : ( tf.se ^ 3 ) ) , le = mp( tf.fi - 1 , (int)( tf.se != 3 ) );
				if( mp( n - tr.fi , (int)( tr.se != 3 ) ) > le ) pp = mp( n , tr.se == 3 ? 1 : ( tr.se ^ 3 ) ) , le = mp( n - tr.fi , (int)( tr.se != 3 ) );
				lsj[i] = pp , ins( 1 , 1 , n , pp );
				printf("%d %d\n",pp.fi,pp.se);
			}
		} else {
			int x; scanf("%d",&x);
			era( 1 , 1 , n , lsj[x] );
		}
	}
}

signed main() {
//	freopen("input","r",stdin);
//	freopen("o.out","w",stdout);
//    int T;cin >> T;while( T-- ) solve();
	solve();
}