#include "expr.h"

#include<ctime>

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxn=+;

int root[maxn],siz[maxn],tr[maxn][],fix[maxn];

bool bz[maxn];

Data key[maxn],num[maxn],wdc;

int i,j,k,l,mid,r,n,m,tot,top;

int newno(int x){

    siz[++tot]=siz[x];tr[tot][]=tr[x][];tr[tot][]=tr[x][];

    fix[tot]=fix[x];bz[tot]=bz[x];key[tot]=key[x];num[tot]=num[x];

    return tot;

}

void update(int x){

    siz[x]=siz[tr[x][]]+siz[tr[x][]]+;

    if(fix[x]<=&&tr[x][]&&tr[x][])

    num[x]=F(num[tr[x][]],num[tr[x][]],fix[x]);

    else num[x]=key[x];

}

void mark(int &x){

    if(!x)return;

    int y=newno(x);

    bz[y]^=;swap(tr[y][],tr[y][]);

    x=y;

}

void pushdown(int x){

    if(bz[x]){mark(tr[x][]);mark(tr[x][]);bz[x]=;}

}

bool cmp(int x,int y){

    if(fix[x]==fix[y])return ((siz[y])<siz[x]);

    else return fix[x]<fix[y];

}

void merge(int l,int r,int &x){

    if(!l||!r){x=l+r;return;}

    pushdown(l);pushdown(r);

    int t;

    if(cmp(l,r)){

        t=newno(l);

        merge(tr[l][],r,tr[t][]);

    }

    else{

        t=newno(r);

        merge(l,tr[r][],tr[t][]);

    }

    update(t);

    x=t;

}

void split(int x,int y,int &l,int &r){

    if(!x){l=r=;return;}

    if(!y){l=;r=x;return;}

    pushdown(x);

    int t;

    if(siz[tr[x][]]>=y){

        split(tr[x][],y,l,r);

        t=newno(x);tr[t][]=r;

        update(t);r=t;

    }

    else{

        split(tr[x][],y-siz[tr[x][]]-,l,r);

        t=newno(x);tr[t][]=l;

        update(t);l=t;

    }

}

void init(int test_id,int n,int m,int k,const Data *a,const int *ops){

    srand(time());

    wdc=a[];top=;int t;

    for(int i=n;i>=;--i){

        t=newno();siz[t]=;fix[t]=;

        key[t]=num[t]=a[i-];

        merge(t,root[],root[]);

        if(i>){

            int t=newno();

            siz[t]=;fix[t]=ops[i-];key[t]=num[t]=wdc;

            merge(t,root[],root[]);

        }

    }

}

Data modify_data(int id,int pos,Data x){

    ++top;++pos;

    split(root[id],*pos-,l,r);

    split(l,*pos-,l,mid);

    int t=newno(mid);

    key[t]=num[t]=x;

    merge(l,t,l);merge(l,r,root[top]);

    return num[root[top]];

}

Data modify_op(int id,int pos,int new_op){

    ++top;

    split(root[id],*pos,l,r);

    split(l,*pos-,l,mid);

    int t=newno(mid);

    fix[t]=new_op;

    merge(l,t,l);merge(l,r,root[top]);

    return num[root[top]];

}

Data reverse(int id,int l,int r){

    ++top;

    ++l,++r;j=l;k=r;

    split(root[id],*k-,l,r);

    split(l,*j-,l,mid);

    mark(mid);

    merge(l,mid,l);

    merge(l,r,root[top]);

    return num[root[top]];

}