On one of the team trainings I've encountered this task. I've not managed to solve it. So I ask you to help me solve this problem.

You are given a sequence $$$a$$$ of length $$$n$$$ and an initially empty set $$$s$$$.

Let $$$\text{xor}(m)$$$ denote the bitwise exclusive OR (XOR) of all elements in the set $$$m$$$, or $$$0$$$ if $$$m$$$ is empty.

Define $$$g(x, m)$$$ as $$$\max(x \oplus \text{xor}(T))$$$, where $$$T$$$ is a subset of $$$m$$$.

Define $$$f(l, r)$$$ as $$$g\left(\bigoplus_{i=l}^r a_i, s \right)$$$. Here, $$$\bigoplus_{i=l}^r a_i$$$ represents the bitwise XOR of all elements in the sequence $$$a$$$ from index $$$l$$$ to $$$r$$$ (inclusive).

The task is to handle queries of the following three types:

1. 1 k v: Replace $$$a_k$$$ with $$$a_k \oplus v$$$.
2. 2 x: Add $$$x$$$ to the set $$$s$$$.
3. 3 l r: Output the least significant $$$64$$$ bits of the value $$$\sum_{i=l}^r f(l, i)$$$.

Input Format:

• The first line contains two integers $$$n$$$ and $$$q$$$ ($$$2 \leq n \leq 5 \times 10^3$$$, $$$1 \leq q \leq 10^5$$$).
• The second line contains $$$n$$$ integers $$$a_i$$$ — the elements of the sequence $$$a$$$ ($$$0 \leq a_i \lt 2^{64}$$$).
• Each of the following $$$q$$$ lines specifies a query in the format described above.
• For a query of type 1 k v: $$$1 \leq k \leq n$$$, $$$0 \leq v \lt 2^{64}$$$.
• For a query of type 2 x: $$$0 \leq x \lt 2^{64}$$$.
• For a query of type 3 l r: $$$1 \leq l \leq r \leq n$$$.