Problem Description

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.

Input Format

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.

Output Format

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

5 5
2 6 4 3 6
A 1 
Q 3 5 4 
A 4
Q 5 7 0 
Q 3 6 6 

4
5
6

Hint

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

Translated by ChatGPT 5