#include<bits/stdc++.h>
using namespace std;
#pragma target("avx512f,sse2,sse3,sse4,sse4.2")
#define ll long long
const int N=500005,inf=1e9;
int n,q,a[N],b[N];
multiset<int>s[N];
int v1[N<<2],v2[N<<2];
#define lc k<<1
#define rc k<<1|1
#define ls lc,l,mid
#define rs rc,mid+1,r
void pushup(int k){
	v1[k]=max(v1[lc],v1[rc]);
	v2[k]=min(v2[lc],v2[rc]);
}
void pre(int k,int l,int r){
	v1[k]=-inf,v2[k]=inf;
	if(l==r) return ;
	int mid=l+r>>1;
	pre(ls),pre(rs);
}
void change(int k,int l,int r,int x,int d1,int d2){
	if(l==r){
		v1[k]=d1,v2[k]=d2;
		return ;
	}
	int mid=l+r>>1;
	if(x<=mid) change(ls,x,d1,d2);
	else change(rs,x,d1,d2);
	pushup(k);
}
int ask1(int k,int l,int r,int x,int y){
	if(x<=l&&r<=y) return v1[k];
	int mid=l+r>>1;
	if(x<=mid&&mid<y) return max(ask1(ls,x,y),ask1(rs,x,y));
	if(x<=mid) return ask1(ls,x,y);
	return ask1(rs,x,y);
}
int ask2(int k,int l,int r,int x,int y){
	if(x<=l&&r<=y) return v2[k];
	int mid=l+r>>1;
	if(x<=mid&&mid<y) return min(ask2(ls,x,y),ask2(rs,x,y));
	if(x<=mid) return ask2(ls,x,y);
	return ask2(rs,x,y);
}
void ins(int x,int y){
	s[x].insert(x-y);
	int z=*s[x].begin();
	change(1,1,n,x,x-z,z);
}
void del(int x,int y){
	s[x].erase(s[x].find(x-y));
	if(!s[x].empty()){
		int z=*s[x].begin();
		change(1,1,n,x,x-z,z);
	}
	else change(1,1,n,x,-inf,inf);
}
bool check(int x,int y,int d){
	if(ask1(1,1,n,x,x+d)>=x) return 1;
	if(x+d+1<=y) if(ask2(1,1,n,x+d+1,y)<=d) return 1;
	return 0;
}
int las=0;
char op[15];
int main(){
	scanf("%d%d",&n,&q);
	pre(1,1,n);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&a[i],&b[i]);
		ins(a[i],b[i]);
	}
	int p,x,y,l,r,mid;
	while(q--){
		scanf("%s",op+1);
		if(op[1]=='U'){
			scanf("%d%d%d",&p,&x,&y);
            p^=las,x^=las,y^=las;
			del(a[p],b[p]);
			a[p]=x,b[p]=y;
			ins(a[p],b[p]);
		}
		else{
			scanf("%d%d",&x,&y);
            x^=las,y^=las;
			if(!check(x,y,y-x)) printf("%d\n",las=0);
			else{
				l=0,r=y-x;
				while(l<r){
					mid=l+r>>1;
					if(check(x,y,mid)) r=mid;
					else l=mid+1;
				}
				printf("%d\n",las=r);
			}
		}
	}
	return 0;
}