Vampiric Powers, anyone?
Contest: Codeforces Round 882 (Div. 2)
Difficulty rating: 1400
Tags: bitmasks, brute force, dp, greedy

DIO knows that the Stardust Crusaders have determined his location and will be coming to fight him. To foil their plans he decides to send out some Stand users to fight them. Initially, he summoned $$$n$$$ Stand users with him, the $$$i$$$-th one having a strength of $$$a_i$$$. Using his vampiric powers, he can do the following as many times as he wishes:

- Let the current number of Stand users be $$$m$$$.
- DIO chooses an index $$$i$$$ ($$$1 \le i \le m$$$).
- Then he summons a new Stand user, with index $$$m+1$$$ and strength given by: $$$$$$a_{m+1} = a_i \oplus a_{i+1} \oplus \ldots \oplus a_m,$$$$$$where the operator $$$\oplus$$$ denotes the bitwise XOR operation.
- Now, the number of Stand users becomes $$$m+1$$$.

Unfortunately for DIO, by using Hermit Purple's divination powers, the Crusaders know that he is plotting this, and they also know the strengths of the original Stand users. Help the Crusaders find the maximum possible strength of a Stand user among all possible ways that DIO can summon.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10\,000$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$)  – the number of Stand users initially summoned.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i < 2^8$$$)  – the strength of each Stand user.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output format:
For each test case, output a single integer, maximum strength of a Stand user among all possible ways that DIO can summon.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, one of the ways to add new Stand users is as follows:

- Choose $$$i=n$$$. Now, $$$a$$$ becomes $$$[0,2,5,1,1]$$$.
- Choose $$$i=1$$$. Now, $$$a$$$ becomes $$$[0,2,5,1,1,7]$$$. $$$7$$$ is the maximum strength of a Stand user DIO can summon.

In the second test case, DIO does not need to add more Stand users because $$$3$$$ is the maximum strength of a Stand user DIO can summon.

Example input:
3
4
0 2 5 1
3
1 2 3
5
8 2 4 12 1

Example output:
7
3
14

Editorial:
At the end of the array, you can only achieve xor of any subarray of the original array.
Proof -
Lets denote $$$f(u,v) =$$$ xor of all $$$a_i$$$ such that $$$min(u,v) \leq i < max(u,v)$$$. In the first operation you add $$$f(n,i)$$$. I.e. $$$[u_1,v_1)=[n,i)$$$. It can be proven that $$$f(u_k,v_k) = f(v_{k-1},v_k)$$$ in the $$$k$$$-th operation which is a range.
Proof -
Suppose we have taken $$$k$$$ ranges that already satisfy this property. Now, I add a new $$$k+1$$$-th range. So, first I need to take the $$$k$$$-th range $$$f(u_k,v_k)$$$. Now I'm xoring it with the range $$$f(u_{k - 1}, v_{k - 1})$$$. As [$$$u_k, v_k$$$) and [$$$u{k - 1}, v_{k - 1}$$$) share an endpoint, the result for these ranges will be a range.
Proof -
For two ranges $$$f(x,y)$$$ and $$$f(y,z)$$$, if the two ranges do not intersect, the result will be the sum of the two ranges $$$f(x,z)$$$. If the two ranges intersect, then the intersections will be cancelled out, and the result will be the difference $$$f(x,z)$$$.
Now, we maintain a boolean array $$$b$$$ where $$$b_i$$$ is $$$1$$$ if there is some $$$j$$$ such that $$$a_1 \oplus a_2 \oplus \cdots \oplus a_j = i$$$. Initially, $$$b$$$ is all $$$0$$$. We loop $$$j$$$ from $$$1$$$ to $$$n$$$ and check for each $$$k$$$ if $$$b_k=1$$$. If it is, then there is some position $$$p < j$$$ such that $$$a_1 \oplus a_2 \oplus \cdots \oplus a_p = k$$$. If we take xor of range from $$$(p,j]$$$, then it will be $$$k \oplus a_1 \oplus a_2 \oplus \cdots \oplus a_j$$$ (as $$$a_1 \oplus a_2 \oplus \cdots \oplus a_p$$$ gets cancelled). This $$$a_1 \oplus a_2 \oplus \cdots \oplus a_j$$$ can be stored as we loop ahead. We are looping all possible prefix xors and not all prefix positions because $$$n$$$ is large.
Time Complexity - $$$O(n \cdot 2^8)$$$.