#335. 4137. [FJOI2015]火星商店问题

4137. [FJOI2015]火星商店问题

[FJOI2015] 火星商店问题

题目描述

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

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

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

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

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

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

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

输入格式

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

接下来的 mm 行,每行表示一个事件。每天的事件按照先事件 00,后事件 11 的顺序排列。

输出格式

对于每个事件 11,输出一行一个整数表示答案。

样例 #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%100\% 的数据,所有输入的整数在 [0,105][0,10^5] 范围内。