P4735 Maximum XOR Sum

You are given a sequence of non-negative integers $\{a\}$ with initial length $N$. There are $M$ operations of the following two types: 1. `A x`: an append operation, meaning that a number $x$ is appended to the end of the sequence, and the length $N$ increases by $1$. 2. `Q l r x`: a query operation. You need to find a position $p$ such that $l \le p \le r$, to maximize $a[p] \oplus a[p+1] \oplus ... \oplus a[N] \oplus x$, and output the maximum value.

The first line contains two integers $N, M$, as described above. The second line contains $N$ non-negative integers, representing the initial sequence $A$. The next $M$ lines each describe one operation, in the format given in the statement.

Suppose there are $T$ query operations. Output $T$ lines, each containing one integer, which is the answer to a query.

- For all test cases, $1 \le N, M \le 3 \times 10 ^ 5$, $0 \le a_i \le 10 ^ 7$. Translated by ChatGPT 5