Your friend, Jackson is invited to a TV show called SuperMemo in which the participant is told to play a memorizing game. At first, the host tells the participant a sequence of numbers, {A₁, A₂, ... A_n}. Then the host performs a series of operations and queries on the sequence which consists:

1. ADD x y D: Add D to each number in sub-sequence {A_x ... A_y}. For example, performing "ADD 2 4 1" on {1, 2, 3, 4, 5} results in {1, 3, 4, 5, 5}
2. REVERSE x y: reverse the sub-sequence {A_x ... A_y}. For example, performing "REVERSE 2 4" on {1, 2, 3, 4, 5} results in {1, 4, 3, 2, 5}
3. REVOLVE x y T: rotate sub-sequence {A_x ... A_y} T times. For example, performing "REVOLVE 2 4 2" on {1, 2, 3, 4, 5} results in {1, 3, 4, 2, 5}
4. INSERT x P: insert P after A_x. For example, performing "INSERT 2 4" on {1, 2, 3, 4, 5} results in {1, 2, 4, 3, 4, 5}
5. DELETE x: delete A_x. For example, performing "DELETE 2" on {1, 2, 3, 4, 5} results in {1, 3, 4, 5}
6. MIN x y: query the participant what is the minimum number in sub-sequence {A_x ... A_y}. For example, the correct answer to "MIN 2 4" on {1, 2, 3, 4, 5} is 2

To make the show more interesting, the participant is granted a chance to turn to someone else that means when Jackson feels difficult in answering a query he may call you for help. You task is to watch the TV show and write a program giving the correct answer to each query in order to assist Jackson whenever he calls.

The first line contains n (n ≤ 100000).

The following n lines describe the sequence.

Then follows M (M ≤ 100000), the numbers of operations and queries.

The following M lines describe the operations and queries.

For each "MIN" query, output the correct answer.

#include <iostream>#include <cstdio>#include <cstring>using namespace std;#define INF 0x7fffffff#define N 1010000struct SplayTree{    int ch[N][2],pre[N],val[N],sz[N],num[N],minx[N],add[N],rev[N];    int top,root;    inline void Rotate(int x,int c)     {        int y=pre[x];        PushDown(y);        PushDown(x);        ch[y][!c]=ch[x][c];        if(ch[x][c]) pre[ch[x][c]]=y;        pre[x]=pre[y];        if(pre[y]) ch[pre[y]][ch[pre[y]][1]==y]=x;        ch[x][c]=y;        pre[y]=x;        PushUp(y);        if(y==root) root=x;    }    inline void Splay(int x,int f)    {         PushDown(x);        while(pre[x]!=f)         {            PushDown(pre[pre[x]]);             PushDown(pre[x]);            PushDown(x);            if(pre[pre[x]]==f) Rotate(x,ch[pre[x]][0]==x);            else            {                int y=pre[x],z=pre[y];                int c=(ch[z][0]==y);                if(ch[y][c]==x) Rotate(x,!c),Rotate(x,c);                else Rotate(y,c),Rotate(x,c);            }        }        PushUp(x);        if(f==0) root=x;    }    inline void SplayKth(int k,int f)    {         int x=root;        k+=1;        while(1)        {            PushDown(x);            if(k==sz[ch[x][0]]+1) break;            else if(k<=sz[ch[x][0]]) x=ch[x][0];            else k-=sz[ch[x][0]]+1,x=ch[x][1];        }        Splay(x,f);    }    inline void AddNode(int x,int c)    {        if(!x) return;        val[x]+=c;        add[x]+=c;        minx[x]+=c;    }    inline void RevNode(int x)    {        if(!x) return;        swap(ch[x][0],ch[x][1]);        rev[x]^=1;    }    inline void PushUp(int x)    {        sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+1;        minx[x]=min(val[x],min(minx[ch[x][0]],minx[ch[x][1]]));    }    inline void PushDown(int x)    {        if(rev[x])        {            RevNode(ch[x][0]);            RevNode(ch[x][1]);            rev[x]=0;        }        if(add[x])        {            AddNode(ch[x][0],add[x]);            AddNode(ch[x][1],add[x]);        }        add[x]=0;    }    inline void NewNode(int &x,int c,int f)    {        x=++top;        sz[x]=1;        ch[x][0]=ch[x][1]=rev[x]=add[x]=0;        val[x]=minx[x]=c;        pre[x]=f;    }    inline void Build(int &x,int l,int r,int f)    {        if(l>r) return;        int m=(l+r)>>1;        NewNode(x,num[m],f);        Build(ch[x][0],l,m-1,x);        Build(ch[x][1],m+1,r,x);        PushUp(x);    }    inline void Init(int n)    {        top=pre[0]=ch[0][0]=ch[0][1]=sz[0]=rev[0]=add[0]=0;        val[0]=minx[0]=INF;        for(int i=1;i<=n;i++) scanf("%d",&num[i]);        Build(root,0,n+1,0);    }    void Ins()    {        int pos,num;        scanf("%d%d",&pos,&num);        SplayKth(pos,0);        SplayKth(pos+1,root);        NewNode(ch[ch[root][1]][0],num,ch[root][1]);        PushUp(ch[root][1]);        PushUp(root);    }    void Del()    {        int pos;        scanf("%d",&pos);        SplayKth(pos-1,0);        SplayKth(pos+1,root);        ch[ch[root][1]][0]=0;        PushUp(ch[root][1]);        PushUp(root);    }    void Rev()    {        int l,r;        scanf("%d%d",&l,&r);        SplayKth(l-1,0);        SplayKth(r+1,root);        RevNode(ch[ch[root][1]][0]);    }    void Add()    {        int l,r,c;        scanf("%d%d%d",&l,&r,&c);        SplayKth(l-1,0);        SplayKth(r+1,root);        AddNode(ch[ch[root][1]][0],c);        PushUp(ch[root][1]);        PushUp(root);    }    void Res()    {        int l,r,t;        scanf("%d%d%d",&l,&r,&t);        int len=r-l+1;        t=(t%len+len)%len;        if(!t) return;        SplayKth(r-t,0);        SplayKth(r+1,root);        int x=ch[ch[root][1]][0];        ch[ch[root][1]][0]=0;        PushUp(ch[root][1]);        PushUp(root);        SplayKth(l-1,0);        SplayKth(l,root);        ch[ch[root][1]][0]=x;        pre[ch[ch[root][1]][0]]=ch[root][1];        PushUp(ch[root][1]);        PushUp(root);    }    void Min()    {        int l,r;        scanf("%d%d",&l,&r);        SplayKth(l-1,0);        SplayKth(r+1,root);        printf("%d\n",minx[ch[ch[root][1]][0]]);    }}t;int main(){    int n,m;    char op[10];    while(scanf("%d",&n)!=EOF)    {        t.Init(n);        scanf("%d",&m);        while(m--)        {            scanf("%s",op);            if(strcmp(op,"INSERT")==0) t.Ins();            else if(strcmp(op,"DELETE")==0) t.Del();            else if(strcmp(op,"ADD")==0) t.Add();            else if(strcmp(op,"REVERSE")==0) t.Rev();            else if(strcmp(op,"MIN")==0) t.Min();            else if(strcmp(op,"REVOLVE")==0) t.Res();        }    }    return 0;}