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 k v: Replace $$$a_k$$$ with $$$a_k \oplus v$$$.2 x: Add $$$x$$$ to the set $$$s$$$.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$$$.
