[FJOI2015] 火星商店问题

题目描述

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

火星人在这条商业街购物时，通常会逛这条商业街某一段路上的所有商店，譬如说商店编号在区间 $[l,r]$ 中的商店，从中挑选一件自己最喜欢的商品。每个火星人对商品的喜好标准各不相同。

通常每个火星人都有一个自己的喜好密码 $x$。对每种标价为 $\text{val}$ 的商品，喜好密码为 $x$ 的火星人对这种商品的喜好程度与 $\text{val}$ 异或 $x$ 的值成正比。也就是说，$\text{val xor }x$ 的值越大，他就越喜欢该商品。

每个火星人的购物卡在所有商店中只能购买最近 $d$ 天内（含当天）进货的商品。另外，每个商店都有一种特殊商品不受进货日期限制，每位火星人在任何时刻都可以选择该特殊商品。每个商店中每种商品都能保证供应，不存在商品缺货的问题。

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

0 s v，表示编号为 $s$ 的商店在当日新进一种标价为 $v$ 的商品。

1 l r x d，表示一位火星人当日在编号在 $[l,r]$ 的商店购买 $d$ 天内的商品，该火星人的喜好密码为 $x$。

输入格式

第一行两个正整数 $n,m$，分别表示商店总数和事件总数。 第二行中有 $n$ 个整数，第 $i$ 个整数表示商店 $i$ 的特殊商品标价。

接下来的 $m$ 行，每行表示一个事件。每天的事件按照先事件 $0$，后事件 $1$ 的顺序排列。

输出格式

对于每个事件 $1$，输出一行一个整数表示答案。

样例 #1

样例输入 #1

4 6
1 2 3 4
1 1 4 1 0
0 1 4
0 1 3
1 1 1 1 0
1 1 1 1 1
1 1 2 1 2

样例输出 #1

5
0
2
5

提示

【数据范围】 对于 $100\%$ 的数据，所有输入的整数在 $[0,10^5]$ 范围内。