[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

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]$ 范围内。