Suffix XOR Queries

Given a non-negative integer sequence \(\{a\}\) of initial length \(N\). You are given \(M\) operations of the following two types:

• A x: Append the number \(x\) to the end of the sequence. The length of the sequence increases by 1.
• Q l r x: Query operation. You need to choose a position \(p\) satisfying \(l \le p \le r\) such that the value \[ a[p] \oplus a[p+1] \oplus \dots \oplus a[N] \oplus x \] is maximized. Here \(\oplus\) denotes the bitwise XOR operation. Output the maximum value.

Note: After each append operation, the suffix XOR values change. Specifically, if the current sequence is \(a_1, a_2, \dots, a_N\) and a new element \(x\) is appended, then for all \(1 \le i \le N\) the updated suffix value becomes \(S[i] = (a[i] \oplus a[i+1] \oplus \dots \oplus a[N]) \oplus x\) and a new suffix value \(S[N+1] = x\) is added.

inputFormat

The first line contains two integers \(N\) and \(M\) separated by a space.

The second line contains \(N\) non-negative integers representing the initial sequence: \(a_1, a_2, \dots, a_N\).

The following \(M\) lines each describe an operation. An operation is either in the form A x or Q l r x as described in the problem.

All indices are 1-indexed.

outputFormat

For each query operation, output a single line containing the maximum value of \(a[p] \oplus a[p+1] \oplus \dots \oplus a[N] \oplus x\) for some index \(p\) with \(l \le p \le r\).

sample

3 3
1 2 3
Q 1 2 4
A 5
Q 1 4 1

5
7