好吧，不得不承认，经过一个寒假的颓废啥都忘了。。
一道裸的splay，但是比赛的时候我一直觉得用splay维护gcd会不会出错。。。。因为我居然觉得旋转过程中gcd无法正确维护。。。。
思路：splay节点信息
on:节点是否是开灯状态
val0:该节点关灯时的值，如果该节点灯开着，那么val0=0,不影响结果。
val1:该节点开灯时的值，如果该节点灯关着，那么val1=0,不影响结果。
gcd0:以该节点为根的子树中所有状态为关的灯的gcd
gcd1:以该节点为根的子树中所有状态为开的灯的gcd
num[0]:以该节点为根的子树有多少个状态为关的灯
num[1]:以该节点为根的子树有多少个状态为开的灯
看来这个月要好好复习了。。。。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define N 500000+100
#define inf 0x3f3f3f3f
inline int max(int a,int b){return a>b?a:b;}
int gcd(int a,int b)
{
    if(a<b) {int t=a;a=b;b=t;}
    return (b==0?a:gcd(b,a%b));
}
struct SplayTree {
#define KT ch[ch[root][1]][0]
#define LC ch[x][0]
#define RC ch[x][1]

	int root;//根节点
	int fa[N];//父亲结点
	int ch[N][2];//孩子结点
	int sz[N];//以结点i为子树的结点数
    int cnt;
    int val0[N],val1[N];
    int on[N];
    int gcd0[N],gcd1[N];
    int data[N],state[N];
    int num[N][2];
	void pushup(int x)
	{
		sz[x]=1+sz[LC]+sz[RC];//如果左子树为空，则LC=0,而sz[0]=0,即如果结点某个结点的子节点不存在，则指向空结点0，空节点的sz=0，不会造成错误
        gcd0[x]=gcd(gcd(gcd0[LC],gcd0[RC]),val0[x]);
        gcd1[x]=gcd(gcd(gcd1[LC],gcd1[RC]),val1[x]);
        num[x][0]=num[LC][0]+num[RC][0]+1-on[x];
        num[x][1]=num[LC][1]+num[RC][1]+on[x];
	}

	void rotate(int x, bool f) //旋转
	{
		int y=fa[x];
		int z=fa[y];
		ch[y][!f]=ch[x][f];
		fa[ch[x][f]]=y;
		fa[x]=z;
		if(z)
		{
			ch[z][ch[z][1]==y]=x;
		}
		ch[x][f]=y;
		fa[y]=x;
		pushup(y);
	}

	void splay(int x, int g) //把结点x转到结点g下
	{
		int y=fa[x];
        while (y!=g)
        {
			int z=fa[y];
			bool f=(ch[y][0]==x);
			if (z!=g && f==(ch[z][0]==y))
			{
				rotate(y,f);
			}
			rotate(x,f);
			y=fa[x];
		}
		pushup(x);
		if(g==0)
		{
			root=x;
		}
	}

	void rotateto(int k,int g) {	//把第k个结点转到结点g下,从第0个开始，因为有附加结点
		int x=root;
		while (sz[LC]!=k)
		{
			if (k<sz[LC])
			{
				x=LC;
			} else
			{
				k-=(sz[LC]+1);
				x=RC;
			}
		}
		splay(x,g);
	}

	void newNode(int &x,int c,int flag)
	{
        x=++cnt;
        on[x]=flag;
        num[x][flag]=1;num[x][1-flag]=0;
        if(!flag) val0[x]=c,val1[x]=0;
        else val1[x]=c,val0[x]=0;
        LC=RC=fa[x]=0;
        gcd0[x]=gcd(gcd(gcd0[LC],gcd0[RC]),val0[x]);
        gcd1[x]=gcd(gcd(gcd1[LC],gcd1[RC]),val1[x]);
        sz[x]=1;
	}

	void makeTree(int &x,int l,int r,int f)
	{
		if (l>r)
		{
			return;
		}
		int m=(l+r)>>1;
		newNode(x,data[m],state[m]);	/*num[m]权值改成题目所需的*/
		makeTree(LC,l,m-1,x);
		makeTree(RC,m + 1,r,x);
		fa[x]=f;
		pushup(x);//建立树的时候，从下往上依次pushup
	}
	void init(int n)
	{
		cnt=0;
		ch[0][0]=ch[0][1]=fa[0]=sz[0]=num[0][0]=num[0][1]=val0[0]=on[0]=val1[0]=gcd0[0]=gcd1[0]=0;//0结点是空节点，代表没有
		//为了方便处理边界,加两个边界顶点
		newNode(root,0,0);
		newNode(ch[root][1],0,0);//这两个边界结点的值不影响正常求解
		fa[cnt]=root;
		sz[root]=2;
		makeTree(KT,1,n,ch[root][1]);
		pushup(ch[root][1]);
		pushup(root);
	}
	int query(int l,int r,int flag)
	{
        rotateto(l-1,0);
        rotateto(r+1,root);
        if(num[KT][flag]==0) return -1;
        return (flag==1?gcd1[KT]:gcd0[KT]);
    }
    void insert(int id,int v,int flag)
    {
        rotateto(id,0);
        rotateto(id+1,root);
        int x=ch[root][1];
        newNode(LC,v,flag);
        fa[LC]=x;
        pushup(x);
        pushup(root);
    }
    void remove(int id)
    {
        rotateto(id-1,0);
        rotateto(id+1,root);
        int x=ch[root][1];
        //fa[LC]=0;
        LC=0;
        pushup(x);
        pushup(root);
    }
    void swap2(int &a,int &b)
    {
        int t=a;a=b;b=t;
    }
    void swap(int x)
    {
        on[x]=1-on[x];
        swap2(val0[x],val1[x]);
        gcd0[x]=gcd(gcd(gcd0[LC],gcd0[RC]),val0[x]);
        gcd1[x]=gcd(gcd(gcd1[LC],gcd1[RC]),val1[x]);
        num[x][0]=num[LC][0]+num[RC][0]+(1-on[x]);
        num[x][1]=num[LC][1]+num[RC][1]+on[x];
    }
    void rev(int id)
    {
        rotateto(id-1,0);
        rotateto(id+1,root);
        int x=ch[root][1];
        swap(KT);
        pushup(x);
        pushup(root);
    }
    void modify(int id,int v)
	{
        rotateto(id-1,0);
        rotateto(id+1,root);
        int x=ch[root][1];
        if(on[LC]==1) val1[LC]=v;
        else val0[LC]=v;
        gcd0[LC]=gcd(gcd(gcd0[ch[LC][0]],gcd0[ch[LC][1]]),val0[LC]);
        gcd1[LC]=gcd(gcd(gcd1[ch[LC][0]],gcd1[ch[LC][1]]),val1[LC]);
        pushup(x);
        pushup(root);
        return;
	}
	void print(int x)
	{
	    if(sz[x]==0) return;
        print(LC);
        printf("on:%d    val0:%d    val1:%d    gcd0:%d   gcd1:%d\n",on[x],val0[x],val1[x],gcd0[x],gcd1[x]);
        print(RC);
	}
	void debug(int x)
	{
        print(x);
        printf("\n");
	}
}spt;
int main()
{
    int i,j;
    int n,m;
    while(~scanf("%d%d",&n,&m))
    {
        for(i=1;i<=n;i++)
            scanf("%d%d",&spt.data[i],&spt.state[i]);
        spt.init(n);
        char com[5];
        int a,b,state;
        while(m--)
        {
            scanf("%s",com);
            if(com[0]=='Q')
            {
                scanf("%d%d%d",&a,&b,&state);
                printf("%d\n",spt.query(a,b,state));
            }
            if(com[0]=='I')
            {
                scanf("%d%d%d",&a,&b,&state);
                spt.insert(a,b,state);
            }
            if(com[0]=='D')
            {
                scanf("%d",&a);
                spt.remove(a);
            }
            if(com[0]=='R')
            {
                scanf("%d",&a);
                spt.rev(a);
            }
            if(com[0]=='M')
            {
                scanf("%d%d",&a,&b);
                spt.modify(a,b);

            }
            //spt.debug(spt.root);
        }
    }
    return 0;
}