Splay

void ins (int x)//!!!!!!!!!!!!
{
	int p=rt;
	if (!p) { rt=add (x,0); return ; }
	while (son(p)[x> w(p)]) p=son(p)[x> w(p)];
	son(p)[x> w(p)]=add (x,p);
	splay (p,0);
}

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdlib>
#include <queue>
#include <cmath>
const int oo=2139063143;
const int N=1010000;
const int P=1000000;
using namespace std;
typedef long long LL;
typedef double db;
//char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
typedef int DATA1;
typedef int DATA2;
inline void sc (DATA1 &x)
{
    x=0; static int p; p=1; static char c; c=getchar();
    while (!isdigit(c)) { if (c=='-') p=-1; c=getchar(); }
    while ( isdigit(c)) { x=(x<<1)+(x<<3)+(c-48); c=getchar(); }
    x*=p;
}
inline void print (DATA2 x)
{
	if (x< 0) putchar('-'),x=-x;
	if (x>=10) print(x/10);
	putchar(x%10+'0');
}
inline void pr (DATA2 x) { print(x),putchar('\n'); }
struct SPLAY { int fa,son[2],siz,w; }t[N]; int tot=0,rt=0;
#define fa(p) t[p].fa
#define son(p) t[p].son
#define w(p) t[p].w
#define siz(p) t[p].siz
int add (int x,int f)
{
	int p=++tot;
	fa(p)=f;
	w(p)=x;
	siz(p)=1;
	return p;
}
void update (int p) { siz(p)=1+siz(son(p)[0])+siz(son(p)[1]); }
int get (int p) { return son(fa(p))[1]==p; }
void rotate (int p)
{
	int f=fa(p),ff=fa(f),s=get (p);
	son(f)[s]=son(p)[s^1];
	if (son(f)[s]) fa(son(f)[s])=f;
	if (ff) son(ff)[son(ff)[1]==f]=p;
	fa(p)=ff;
	son(p)[s^1]=f,fa(f)=p;
	update (f),update (p);
}
void splay (int p,int to)
{
	while (fa(p)!=to)
	{
		int f=fa(p);
		if (fa(f)!=to) rotate (get (p)==get (f)?f:p);
		rotate (p);
	}
	if (to==0) rt=p;
}
int find (int p,int x)
{
	int ls=son(p)[0],rs=son(p)[1];
	if (w(p)==x) return p;
	return (x< w(p))?(ls?find (ls,x):p):(rs?find (rs,x):p);
}//the nearest
int findpre (int x)
{
	int p=find (rt,x);
	splay (p,0);//!!!
	if (w(p)< x||!son(p)[0]) return p;
	p=son(p)[0];
	while (son(p)[1]) p=son(p)[1];
	return p;
}
int findnxt (int x)
{
	int p=find (rt,x);
	splay (p,0);//!!!
	if (w(p)> x||!son(p)[1]) return p;
	p=son(p)[1];
	while (son(p)[0]) p=son(p)[0];
	return p;
}
void ins (int x)//!!!!!!!!!!!!
{
	int p=rt;
	if (!p) { rt=add (x,0); return ; }
	while (son(p)[x> w(p)]) p=son(p)[x> w(p)];
	son(p)[x> w(p)]=add (x,p);
	splay (p,0);
}
void del (int x)
{
	int l=findpre (x),r=findnxt (x);
	splay (l,0),splay (r,l);
	son(r)[0]=0;
	update (r),update (l);
}
int main()
{
	//freopen (".in","r",stdin);
	//freopen (".out","w",stdout);
	ins (-oo),ins (oo);
	int n; sc(n);
	int cur=-1;
	int ans=0;
	while (n--)
	{
		int op,x; sc(op),sc(x);
		if (cur==-1) ins (x),cur=op;
		else if (cur==op) ins (x);
		else
		{
			del (x);
			int pre=findpre (x),nxt=findnxt (x);
			pre=w(pre),nxt=w(nxt);
			LL s1=abs ((LL)x-pre),s2=abs ((LL)x-nxt);
			if (s1<=s2) del (pre),ans+=s1;
			else del (nxt),ans+=s2;
			if (siz(rt)==2) cur=-1;
		}
		ans%=P;
	}
	pr(ans);
	return 0;
}

#include <bits/stdc++.h>
#define pr(p) printf("%d\n",p)
const int oo=2139063143;
const int N=1010000;
const int mod=1000000007;
using namespace std;
typedef long long LL;
inline void sc (int &x)
{
    x=0; static int p; p=1; static char c; c=getchar();
    while (!isdigit(c)) { if (c=='-') p=-1; c=getchar(); }
    while ( isdigit(c)) { x=(x<<1)+(x<<3)+(c-48); c=getchar(); }
    x*=p;
}
struct SPLAY
{
    int fa,son[2],siz,laz1,laz2,sam,w;
    int sum,lmax,rmax,maxx,ma;
}t[N]; int tot=0,root;
#define fa(p) t[p].fa
#define son(p) t[p].son
#define siz(p) t[p].siz
#define laz1(p) t[p].laz1
#define laz2(p) t[p].laz2
#define sam(p) t[p].sam
#define w(p) t[p].w
#define sum(p) t[p].sum
#define lmax(p) t[p].lmax
#define rmax(p) t[p].rmax
#define maxx(p) t[p].maxx
#define ma(p) t[p].ma
int tmp[N],las[N];
int add (int x,int f)
{
    int p=las[0]?las[las[0]--]:++tot;
    fa(p)=f;
    son(p)[0]=son(p)[1]=laz1(p)=laz2(p)=sam(p)=0;
    siz(p)=1; w(p)=sum(p)=ma(p)=x;
    lmax(p)=rmax(p)=maxx(p)=max (x,0);
    return p;
}
void update (int p)
{
    siz(p)=1; sum(p)=ma(p)=w(p);
    int ls=son(p)[0],rs=son(p)[1];
    siz(p)+=siz(ls)+siz(rs),sum(p)+=sum(ls)+sum(rs);
    if (ls) ma(p)=max (ma(p),ma(ls));
    if (rs) ma(p)=max (ma(p),ma(rs));
    lmax(p)=max (lmax(ls),max (sum(ls)+w(p),sum(ls)+w(p)+lmax(rs)));
    rmax(p)=max (rmax(rs),max (sum(rs)+w(p),sum(rs)+w(p)+rmax(ls)));
    maxx(p)=max (max (maxx(ls),maxx(rs)),rmax(ls)+w(p)+lmax(rs));
}
void updatesame (int p,int d)
{
    sum(p)=d*siz(p),sam(p)=w(p)=ma(p)=d,laz2(p)=1;
    if (d> 0) lmax(p)=rmax(p)=maxx(p)=sum(p);
    else lmax(p)=rmax(p)=0,maxx(p)=d;
}
void updaterev (int p)
{
    laz1(p)^=1;
    swap (son(p)[0],son(p)[1]),swap (lmax(p),rmax(p));
}
void push (int p)
{
    int ls=son(p)[0],rs=son(p)[1];
    if (laz2(p))
    {
	updatesame (ls,sam(p)),updatesame (rs,sam(p));
	ma(p)=sam(p);
	laz1(p)=laz2(p)=sam(p)=0;
    }
    if (laz1(p)) updaterev (ls),updaterev (rs),laz1(p)=0;
}
int build (int l,int r,int f)
{
    int mid=(l+r)>>1,p=add (tmp[mid],f);
    if (l< mid) son(p)[0]=build (l,mid-1,p);
    if (r> mid) son(p)[1]=build (mid+1,r,p);
    update (p);
    return p;
}
int get(int p) { return son(fa(p))[1]==p; }
void rotate (int p)
{
    int f=fa(p),ff=fa(f),s=get(p);
    son(f)[s]=son(p)[s^1];
    if (son(f)[s]) fa(son(f)[s])=f;
    son(p)[s^1]=f,fa(f)=p;
    if (ff) son(ff)[son(ff)[1]==f]=p;
    fa(p)=ff;
    update (f),update (p);
}
void splay (int p,int to)
{
    while (fa(p)!=to)
    {
	int f=fa(p),ff=fa(f);
	if (ff!=to)
	    rotate (get(p)==get(f)?f:p);
	rotate (p);
    }
    if (to==0) root=p;
}
int find (int p,int k)
{
    push (p);
    int ls=son(p)[0],rs=son(p)[1];
    if (siz(ls)+1==k) return p;
    if (siz(ls)  >=k) return find (ls,k);
    return find (rs,k-siz(ls)-1);
}
void insqujian (int l,int len)
{
    int x=find (root,l),y=find (root,l+1);
    splay (x,0),splay (y,x);
    son(y)[0]=build (1,len,y);
    update (y),update (x);
}
void reverse (int l,int r)
{
    int x=find (root,l),y=find (root,r+2);
    splay (x,0),splay (y,x);
    int ls=son(y)[0];
    laz1(ls)^=1;
    swap (son(ls)[0],son(ls)[1]),swap (lmax(ls),rmax(ls));
    update (y),update (x);
}
void collect (int p)
{
    if (!p) return ;
    las[++las[0]]=p;
    int ls=son(p)[0],rs=son(p)[1];
    collect (ls),collect (rs);
}
void clear (int p)
{
    collect (p);
    fa(p)=son(p)[0]=son(p)[1]=siz(p)=w(p)=laz1(p)=laz2(p)=sam(p)=sum(p)=maxx(p)=lmax(p)=rmax(p)=0;
    ma(p)=-oo;
}
void del (int l,int r)
{
    int x=find (root,l),y=find (root,r+2);
    splay (x,0),splay (y,x);
    clear (son(y)[0]),son(y)[0]=0;
    update (y),update (x);
}
int getsum (int l,int r)
{
    int x=find (root,l),y=find (root,r+2);
    splay (x,0),splay (y,x);
    return sum(son(y)[0]);
}
void makesame (int l,int r,int k)
{
    int x=find (root,l),y=find (root,r+2);
    splay (x,0),splay (y,x);
    updatesame (son(y)[0],k);
    update (y),update (x);
}
int maxsum (int l,int r)
{
    int x=find (root,l),y=find (root,r+2);
    splay (x,0),splay (y,x);
    int ls=son(y)[0];
    if (ma(ls)< 0) return ma(ls);
    return maxx (ls);
}
int main()
{
    //freopen (".in","r",stdin);
    //freopen (".out","w",stdout);
    int n,m; sc(n),sc(m);
    for (int i=1; i<=n; i++) sc(tmp[i]);
    tmp[0]=tmp[n+1]=-oo/5;
    for (int i=0; i<=n*2; i++)
	ma(i)=-oo;
    root=build (0,n+1,0);
    int num=n;
    for (int i=1; i<=m; i++)
    {
	char s[10]; scanf ("%s",s);
	if (s[2]=='X') { pr(maxsum (1,num)); continue; }
	int pos,tf; sc(pos),sc(tf);
	if (s[0]=='I')
	{
	    for (int j=1; j<=tf; j++) sc(tmp[j]);
	    insqujian (pos+1,tf);
	    num+=tf;
	}
	if (s[0]=='D') del (pos,pos+tf-1),num-=tf;
	if (s[2]=='K')
	{
	    int c; sc(c);
	    makesame (pos,pos+tf-1,c);
	}
	if (s[0]=='G') pr(getsum (pos,pos+tf-1));
	if (s[0]=='R') reverse (pos,pos+tf-1);
    }

    return 0;
}