#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define rij register int j

#define rii register int i

#define rs 65536

using namespace std;

struct tree{

    int fz,qf,val;

}x[];

int n,k,q,t,bs[];

void ycl()

{

    bs[]=;

    for(rii=;i<=;i++)

    {

        bs[i]=bs[i-]*;

    }

}

void cf(int val)

{

    unsigned int kkk=val;

    while(kkk!=)

    {

        cout<<kkk%<<" ";

        kkk/=;

    }

    cout<<endl;

}

int qf(int val)

{

    int bs=(<<k);

    int ltt=val%bs;

    val-=ltt;

    ltt=-ltt;

    ltt--;

    unsigned kkk=ltt;

    kkk%=bs;

    return val+kkk;

}

int fz(int val)

{

    int bis=(<<k);

    int ltt=val%bis;

    int v=;

    val-=ltt;

    for(rii=;i<=k;i++)

    {

        v+=(ltt%)*bs[k-i];

        ltt/=;

    }

    return val+v;

}

void add(int wz,int nl,int nr,int val,int bh)

{

    if(wz==nl&&wz==nr)

    {

        x[bh].val=val;

        return;

    }

    int mid=(nl+nr)/;

    if(wz<=mid)

    {

        add(wz,nl,mid,val,bh*);

    }

    else

    {

        add(wz,mid+,nr,val,bh*+);

    }

}

void change1(int l,int r,int nl,int nr,int bh)

{

    if(l<nl)

    {

        l=nl;

    }

    if(r>nr)

    {

        r=nr;

    }

    if(l==nl&&r==nr)

    {

        x[bh].qf++;

        x[bh].qf%=;

        return;

    }

    int mid=(nl+nr)/;

    if(l<=mid)

    {

        change1(l,r,nl,mid,bh*);

    }

    if(r>mid)

    {

        change1(l,r,mid+,nr,bh*+);

    }

}

void change2(int l,int r,int nl,int nr,int bh)

{

    if(l<nl)

    {

        l=nl;

    }

    if(r>nr)

    {

        r=nr;

    }

    if(l==nl&&r==nr)

    {

        x[bh].fz++;

        x[bh].fz%=;

        return;

    }

    int mid=(nl+nr)/;

    if(l<=mid)

    {

        change2(l,r,nl,mid,bh*);

    }

    if(r>mid)

    {

        change2(l,r,mid+,nr,bh*+);

    }

}

int query(int wz,int nl,int nr,int bh,int lazy1,int lazy2)

{

    lazy1%=;

    lazy2%=;

    if(wz==nl&&wz==nr)

    {

        lazy1+=x[bh].qf;

        lazy2+=x[bh].fz;

        int ltt=x[bh].val;

        if(lazy1==)

        {

            ltt=qf(ltt);

        }

        if(lazy2==)

        {

            ltt=fz(ltt);

        }

        return ltt;

    }

    int mid=(nl+nr)/;

    if(wz<=mid)

    {

        return query(wz,nl,mid,bh*,lazy1+x[bh].qf,lazy2+x[bh].fz);

    }

    else

    {

        return query(wz,mid+,nr,bh*+,lazy1+x[bh].qf,lazy2+x[bh].fz);

    }

}

void pd(int wz,int l,int r)

{

    if(l==r)

    {

        if(x[wz].fz!=)

        {

            x[wz].fz=;

            x[wz].val=fz(x[wz].val);

        }

        if(x[wz].qf!=)

        {

            x[wz].qf=;

            x[wz].val=qf(x[wz].val);

        }

        return;

    }

    if(x[wz].fz!=)

    {

        x[wz*].fz++;

        x[wz*].fz%=;

        x[wz*+].fz++;

        x[wz*+].fz%=;

    }

    if(x[wz].qf!=)

    {

        x[wz*].qf++;

        x[wz*].qf%=;

        x[wz*+].qf++;

        x[wz*+].qf%=;

    }

    x[wz].qf=;

    x[wz].fz=;

    int mid=(l+r)/;

    pd(wz*,l,mid);

    pd(wz*+,mid+,r);

}

int main()

{

//     freopen("XiaoX10.in","r",stdin);

//     freopen("XiaoX10.out","w",stdout);

    ycl();

    scanf("%d%d",&n,&t);

    for(rii=;i<=n;i++)

    {

        int val;

        scanf("%d",&val);

        add(i,,rs,val,);

    }

    for(rii=;i<=t;i++)

    {

        if(i!=)

        {

            pd(,,rs);

        }

        scanf("%d%d",&q,&k);

        int pid,l,r,wz;

        for(rij=;j<=q;j++)

        {

            scanf("%d",&pid);

            if(pid==)

            {

                scanf("%d%d",&l,&r);

                change1(l,r,,rs,);

            }

            if(pid==)

            {

                scanf("%d%d",&l,&r);

                change2(l,r,,rs,);

            }

            if(pid==)

            {

                scanf("%d",&wz);

                int ltt=query(wz,,rs,,,);

                printf("%d\n",ltt);

            }

        }

    }

    k=;

}