"Training Team Mutual Test" is an open algorithm competition game independently developed by CCF. Here, the strongest contestants will become "Jiji Kings," guiding the power of OI, defeating powerful problems, and retrieving lost IOI gold medals.

To become a "Jiji King," you must first defeat "The Xor Master."

"The Xor Master" has challenged you:

In the following, the XOR operator is denoted as $ \oplus $.

"The Xor Master" has a sequence $ a $ of length $ n $ and an initially empty set $ S_0 $.

Define $ \operatorname{xor}(S) $ as the XOR sum of all elements in set $ S $, and $ 0 $ if $ S $ is empty.

Define $ g(x,S)=\max\limits_{T\subseteq S} (x\oplus \operatorname{xor}(T)) $.

Define $ f(l,r)=g(\oplus_{i=l}^{r} a_i, S_0) $, where $ \oplus_{i=l}^{r}a_i $ denotes the XOR sum of $ a_l \sim a_r $.

"The Xor Master" will perform $ Q $ operations or queries:

• 1 x v: XOR $ a_x $ with $ v $.
• 2 x: Add $ x $ to the set $ S_0 $.
• 3 l r: Query the value of $ \sum\limits_{i=l}^r f(l,i) $. Since the answer can be very large, you only need to output the answer modulo $ 2^{64} $.

You are eager to become a "Jiji King," so please quickly answer "The Xor Master's" queries to defeat him!

Input

The first line contains two integers $ n, Q $. The second line contains $ n $ non-negative integers $ a_1 \sim a_n $. The next $ Q $ lines each describe an operation or query, with the format as described in the problem statement.

Output

For each query, output a single integer on a new line representing the answer modulo $ 2^{64} $.

Examples

Input 1

5 5
5 7 1 4 3
3 1 3
1 2 4
3 1 5
2 3
3 1 5

Output 1

10
21
25

Input 2

5 6
0 6 9 8 3
3 2 5
1 3 6
3 2 5
1 4 1
2 3
3 1 5

Output 2

32
18
25

Constraints

• Special Property $ \mathrm{A} $: No type 1 operations exist.
• Special Property $ \mathrm{B} $: No type 2 operations exist.
• Special Property $ \mathrm{C} $: For all queries, it is guaranteed that $ l=1 $.