题目描述

给定一个长度为 $n$ 的数组 $a$。你需要处理以下几类操作：

• upd and l r x：对所有 $l \le i \le r$，执行 $a_i = a_i \& x$；
• upd or l r x：对所有 $l \le i \le r$，执行 $a_i = a_i | x$；
• upd xor l r x：对所有 $l \le i \le r$，执行 $a_i = a_i \oplus x$；
• get and l r：求所有 $l \le i \le r$ 的 $a_i$ 的按位与；
• get or l r：求所有 $l \le i \le r$ 的 $a_i$ 的按位或；
• get xor l r：求所有 $l \le i \le r$ 的 $a_i$ 的按位异或。

其中 & 表示按位与，| 表示按位或，xor / $\oplus$ 表示按位异或。

输入格式

第一行输入两个整数 $n,q$，表示数组长度和操作数量。

第二行输入 $n$ 个整数：

接下来 $q$ 行，每行按照题目描述中的格式给出一个操作。

输出格式

对于每个 get 操作，输出对应答案。保证每个测试中至少有一个 get 操作。

数据范围

对于所有测试数据：

对于修改操作中的 $x$：

且：

样例

输入

10 10
5 7 3 10 12 0 11 15 14 31
get or 3 7
get xor 2 9
upd and 1 5 14
upd xor 3 10 7
get xor 1 10
get and 9 10
upd or 3 8 6
get xor 1 10
get or 5 5
get xor 4 6

输出

15
8
19
8
19
15
7

评分方式

测试点分为 9 组。注意，部分测试组不要求通过样例组。只有通过某一组的全部测试，并通过该组依赖的必要组，才能获得该组分数。