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 < 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 < 2^{64}$. ↵
- For a query of type **`2 x`**: $0 \leq x < 2^{64}$. ↵
- For a query of type **`3 l r`**: $1 \leq l \leq r \leq n$. ↵
↵
---↵
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 < 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 < 2^{64}$. ↵
- For a query of type **`2 x`**: $0 \leq x < 2^{64}$. ↵
- For a query of type **`3 l r`**: $1 \leq l \leq r \leq n$. ↵
