火星上的一条商业街里按照商店的编号1，2 ，…，n ，依次排列着n个商店。商店里出售的琳琅满目的商品中，每种商品都用一个非负整数val来标价。每个商店每天都有可能进一些新商品，其标价可能与已有商品相同。 

火星人在这条商业街购物时，通常会逛这条商业街某一段路上的所有商店，譬如说商店编号在区间[L,R]中的商店，从中挑选1件自己最喜欢的商品。每个火星人对商品的喜好标准各不相同。通常每个火星人都有一个自己的喜好密码x。对每种标价为val的商品，喜好密码为x的火星人对这种商品的喜好程度与val异或x的值成正比。也就是说，val xor x的值越大，他就越喜欢该商品。每个火星人的购物卡在所有商店中只能购买最近d天内（含当天）进货的商品。另外，每个商店都有一种特殊商品不受进货日期限制，每位火星人在任何时刻都可以选择该特殊商品。每个商店中每种商品都能保证供应，不存在商品缺货的问题。 

对于给定的按时间顺序排列的事件，计算每个购物的火星人的在本次购物活动中最喜欢的商品，即输出val xor x的最大值。这里所说的按时间顺序排列的事件是指以下2种事件： 

事件0，用三个整数0,s,v，表示编号为s的商店在当日新进一种标价为v 的商品。 

事件1，用5个整数1,L,R,x,d，表示一位火星人当日在编号为L到R的商店购买d天内的商品，该火星人的喜好密码为x。

第1行中给出2个正整数n,m，分别表示商店总数和事件总数。 

将计算出的每个事件1的val xor x的最大值依次输出。

n, m <= 100000

数据中，价格不大于100000

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<vector>

 #include<cstring>

 #define M 100010

 #define ls node<<1

 #define rs node<<1|1

 using namespace std;

 int n,m,cnt,cnt1,cnt2;

 int rt[M],f[M],ans[M];

 vector<int>seg[M<<];

 struct CG{int s,v,t;}q[M],tmp1[M],tmp2[M];

 struct ASK{int l,r,l1,r1,x;}p[M];

 bool cmp(CG a1,CG a2) {return a1.s<a2.s;}

 struct Trie

 {

     int cnt;

     int val[M<<],ch[M<<][];

     void insert(int &now,int pre,int w,int o)

     {

         now=++cnt,val[now]=val[pre]+;

         ch[now][]=ch[pre][];ch[now][]=ch[pre][];

         if(o==-) return;bool c=w&(<<o);

         insert(ch[now][c],ch[pre][c],w,o-);

     }

     int query(int now,int pre,int w,int o)

     {

         if(o==-) return ;

         bool c=w&(<<o);

         int tmp=val[ch[now][c^]]-val[ch[pre][c^]];

         if(tmp) return query(ch[now][c^],ch[pre][c^],w,o-)+(<<o);

         else return query(ch[now][c],ch[pre][c],w,o-);

     }

 }T;

 void insert(int node,int l,int r,int l1,int r1,int id)

 {

     if(l1>r1) return;

     if(l1<=l&&r1>=r) {seg[node].push_back(id);return;}

     int mid=(l+r)/;

     if(l1<=mid) insert(ls,l,mid,l1,r1,id);

     if(r1>mid) insert(rs,mid+,r,l1,r1,id);

 }

 int get(int v)

 {

     int l=,r=cnt,ans=;

     while(l<=r)

     {

         int mid=(l+r)/;

         if(f[mid]<=v) ans=mid,l=mid+;

         else r=mid-;

     }

     return ans;

 }

 void cal(int node,int l,int r)

 {

     cnt=T.cnt=;

     for(int i=l;i<=r;i++)

     {

         f[++cnt]=q[i].s;

         T.insert(rt[cnt],rt[cnt-],q[i].v,);

     }

     for(int i=;i<seg[node].size();i++)

     {

         int id=seg[node][i];

         int l=get(p[id].l-);

         int r=get(p[id].r);

         ans[id]=max(ans[id],T.query(rt[r],rt[l],p[id].x,));

     }

 }

 void solve(int node,int l,int r,int l1,int r1)

 {

     if(l1>r1) return;

     cal(node,l,r);

     if(l==r) return;

     int mid=(l+r)/,t1=,t2=;

     for(int i=l1;i<=r1;i++)

     {

         if(q[i].t<=mid) tmp1[++t1]=q[i];

         else tmp2[++t2]=q[i];

     }

     for(int i=;i<=t1;i++) q[i+l1-]=tmp1[i];

     for(int i=;i<=t2;i++) q[i+l1-+t1]=tmp2[i];

     solve(ls,l,mid,l1,l1+t1-);

     solve(rs,mid+,r,l1+t1,r1);

 }

 int main()

 {

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

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

     {

         int x;scanf("%d",&x);

         T.insert(rt[i],rt[i-],x,);

     }

     for(int i=;i<=m;i++)

     {

         int opt;scanf("%d",&opt);

         if(!opt)

         {

             int s,v;scanf("%d%d",&s,&v);

             cnt1++;q[cnt1]=(CG){s,v,cnt1};

         }

         else

         {

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

             ans[++cnt2]=T.query(rt[r],rt[l-],x,);

             p[cnt2]=(ASK){l,r,max(,cnt1-d+),cnt1,x};

         }

     }

     for(int i=;i<=cnt2;i++)

         insert(,,cnt1,p[i].l1,p[i].r1,i);

     sort(q+,q++cnt1,cmp);

     solve(,,cnt1,,cnt1);

     for(int i=;i<=cnt2;i++) printf("%d\n",ans[i]);

     return ;

 }