Given an array arr[] of size, N. Find the subarray with maximum XOR. A subarray is a contiguous part of the array.
Example 1:
Input:
N = 4
arr[] = {1,2,3,4}
Output: 7
Explanation: 
The subarray {3,4} has maximum xor 
value equal to 7.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function maxSubarrayXOR() which takes the array arr[], its size N as input parameters and returns the maximum xor of any subarray.
 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
 
Constraints:
1 <= N <= 10^{5}
1^{ }<= arr[i] <= 10^{5}

Difficulty: MEDIUM
Tags: String algorithms

Data structures
Skill types: Data structures
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)

Starter code:
#User function Template for python3

class Solution:
    def maxSubarrayXOR (self, N, arr):
        # code here 
        
        

Solutions:
class TrieNode:

	def __init__(self):
		self.bits = {}
		self.val = None

class Trie:

	def __init__(self) -> None:
		self.root = TrieNode()

	def insert(self, n):
		curr_node = self.root
		for i in range(31, -1, -1):
			bitVal = n >> i & 1
			if bitVal not in curr_node.bits:
				curr_node.bits[bitVal] = TrieNode()
			curr_node = curr_node.bits[bitVal]
		curr_node.val = n

	def _find_Max_XOR(self, n):
		curr_node = self.root
		for i in range(31, -1, -1):
			bitVal = n >> i & 1
			if 1 - bitVal in curr_node.bits:
				curr_node = curr_node.bits[1 - bitVal]
			elif bitVal in curr_node.bits:
				curr_node = curr_node.bits[bitVal]
			else:
				return 0
		return n ^ curr_node.val

	def maxXorSubarray(self, arr):
		max_xor = arr[0]
		prefix_xor = arr[0]
		self.insert(prefix_xor)
		for n in arr[1:]:
			prefix_xor = prefix_xor ^ n
			max_xor = max(max_xor, prefix_xor, self._find_Max_XOR(prefix_xor))
			self.insert(prefix_xor)
		return max_xor

class Solution:

	def maxSubarrayXOR(self, N, arr):
		t = Trie()
		return t.maxXorSubarray(arr)


import math

class Solution:

	def maxSubarrayXOR(self, N, arr):
		pref_xor = [None] * (N + 1)
		pref_xor[0] = 0
		t = 0
		for i in range(N):
			t ^= arr[i]
			pref_xor[i + 1] = t

		def insert(root, bin_str):
			for bit_chr in bin_str:
				bit = int(bit_chr)
				if bit not in root:
					root[bit] = {}
				root = root[bit]

		def findMaxXor(root, bin_str):
			target_bin_str = ''.join(('0' if c == '1' else '1' for c in bin_str))
			best_str = ''
			for bit_chr in target_bin_str:
				bit = int(bit_chr)
				if bit in root:
					best_str += str(bit)
					root = root[bit]
				else:
					best_str += str(1 ^ bit)
					root = root[1 ^ bit]
			best = int(best_str, 2)
			num = int(bin_str, 2)
			return best ^ num
		max_num = max(pref_xor)
		k = math.floor(math.log(max_num, 2)) + 1
		for (i, num) in enumerate(pref_xor):
			pref_xor[i] = bin(num)[2:].zfill(k)
		trie = {}
		max_xor = 0
		for num_str in pref_xor:
			insert(trie, num_str)
			max_xor = max(max_xor, findMaxXor(trie, num_str))
		return max_xor


class Solution:

	def maxSubarrayXOR(self, n, a):

		class Trie:

			def __init__(self):
				self.left = None
				self.right = None

		def Insert(root, n):
			for i in range(31, -1, -1):
				val = n >> i & 1
				if val == 0:
					if root.left == None:
						root.left = Trie()
					root = root.left
				else:
					if root.right == None:
						root.right = Trie()
					root = root.right

		def Max_Xor_SubArr(root, a, n):
			maxor = 0
			prevxor = 0
			for i in a:
				currnod = root
				currxor = 0
				val = i ^ prevxor
				for j in range(31, -1, -1):
					bit = val >> j & 1
					if bit == 0:
						if currnod.right:
							currxor += 1 << j
							currnod = currnod.right
						elif currnod.left:
							currnod = currnod.left
						else:
							break
					elif currnod.left:
						currxor += 1 << j
						currnod = currnod.left
					elif currnod.right:
						currnod = currnod.right
					else:
						break
				prevxor ^= i
				maxor = max(maxor, currxor, prevxor)
				Insert(root, prevxor)
			return maxor
		root = Trie()
		return Max_Xor_SubArr(root, a, n)


INT = 32
INT_VAL = 2 ** (INT - 1)

class Node:

	def __init__(self) -> None:
		self.left = None
		self.right = None

class BST:

	def __init__(self) -> None:
		self.root = Node()

	def add(self, num):
		val = INT_VAL
		node = self.root
		while val > 0:
			if val & num != 0:
				if node.right is None:
					node.right = Node()
				node = node.right
			else:
				if node.left is None:
					node.left = Node()
				node = node.left
			val >>= 1

	def query(self, num):
		val = INT_VAL
		node = self.root
		res = 0
		while val > 0:
			if val & num != 0:
				if not node.left is None:
					node = node.left
				else:
					res += val
					node = node.right
			elif not node.right is None:
				res += val
				node = node.right
			else:
				node = node.left
			val >>= 1
		return res

class Solution:

	def maxSubarrayXOR(self, N, arr):
		tree = BST()
		tree.add(0)
		pre_xor = 0
		best = float('-inf')
		for i in range(N):
			pre_xor ^= arr[i]
			local_best = pre_xor ^ tree.query(pre_xor)
			best = max(best, local_best)
			tree.add(pre_xor)
		return best


class BinaryTrie:

	def __init__(self, max_bit_len=32):
		self.inf = 1 << 63
		self.cc = [0]
		self.to = [[-1], [-1]]
		self.mb = max_bit_len

	def add(self, a):
		u = 0
		self.cc[u] += 1
		for i in range(self.mb - 1, -1, -1):
			d = a >> i & 1
			if self.to[d][u] == -1:
				self.to[d][u] = len(self.cc)
				self.to[0].append(-1)
				self.to[1].append(-1)
				self.cc.append(0)
			u = self.to[d][u]
			self.cc[u] += 1

	def remove(self, a):
		if self.cc[0] == 0:
			return False
		uu = [0]
		u = 0
		for i in range(self.mb - 1, -1, -1):
			d = a >> i & 1
			u = self.to[d][u]
			if u == -1 or self.cc[u] == 0:
				return False
			uu.append(u)
		for u in uu:
			self.cc[u] -= 1
		return True

	def cnt(self, a):
		u = 0
		for i in range(self.mb - 1, -1, -1):
			d = a >> i & 1
			u = self.to[d][u]
			if u == -1 or self.cc[u] == 0:
				return 0
		return self.cc[u]

	def min_xor(self, a):
		if self.cc[0] == 0:
			return self.inf
		(u, res) = (0, 0)
		for i in range(self.mb - 1, -1, -1):
			d = a >> i & 1
			v = self.to[d][u]
			if v == -1 or self.cc[v] == 0:
				res |= 1 << i
				u = self.to[d ^ 1][u]
			else:
				u = v
		return res

	def max_xor(self, a):
		if self.cc[0] == 0:
			return -self.inf
		(u, res) = (0, 0)
		for i in range(self.mb - 1, -1, -1):
			d = a >> i & 1
			v = self.to[d ^ 1][u]
			if v == -1 or self.cc[v] == 0:
				u = self.to[d][u]
			else:
				u = v
				res |= 1 << i
		return res

class Solution:

	def maxSubarrayXOR(self, N, arr):
		trie = BinaryTrie()
		trie.add(0)
		x = 0
		for i in arr:
			x ^= i
			trie.add(x)
		X = x
		ans = 0
		x = 0
		for i in arr[::-1]:
			x ^= i
			z = trie.max_xor(X ^ x)
			ans = max(ans, z)
		return ans


class Solution:

	def maxSubarrayXOR(self, N, arr):

		class Node:

			def __init__(self):
				self.ch = [None] * 2
		root = Node()

		def insert(root, A):
			temp = root
			for i in range(21, -1, -1):
				bit = 0
				if 1 << i & A:
					bit = 1
				if temp.ch[bit] == None:
					temp.ch[bit] = Node()
				temp = temp.ch[bit]
		p = 0
		insert(root, p)
		ans = 0
		for j in arr:
			p ^= j
			temp = root
			mx = 0
			for i in range(21, -1, -1):
				bit = 0
				if 1 << i & p:
					bit = 1
				if bit == 1:
					if temp.ch[0]:
						mx += 1 << i
						temp = temp.ch[0]
					else:
						temp = temp.ch[1]
				elif temp.ch[1]:
					mx += 1 << i
					temp = temp.ch[1]
				else:
					temp = temp.ch[0]
			insert(root, p)
			ans = max(ans, mx)
		return ans


class Solution:

	def maxSubarrayXOR(self, N, arr):
		ans = 1
		max_sum = -100
		for i in range(N):
			if N == 1:
				return arr[0]
			if arr[i] == arr[i - 1]:
				return arr[i - 1]
			ans = max(arr[i], arr[i] ^ ans)
			max_sum = max(max_sum, ans)
		return max_sum


class Trie_Node:

	def __init__(self):
		self.edges = {}
		self.val = 0

class Trie:

	def __init__(self, n):
		self.root = Trie_Node()
		self.max_len = n

	def insert(self, cur_val):
		cur_node = self.root
		for j in range(self.max_len, -1, -1):
			val = 1 if cur_val & 1 << j else 0
			if val not in cur_node.edges:
				cur_node.edges[val] = Trie_Node()
			cur_node = cur_node.edges[val]
		cur_node.val = cur_val

class Solution:

	def maxSubarrayXOR(self, n, arr):
		ans = float('-inf')
		A = [None] * (len(arr) + 1)
		A[0] = 0
		for i in range(1, len(arr) + 1):
			A[i] = A[i - 1] ^ arr[i - 1]
		max_len = len(bin(max(A))) - 2
		trie = Trie(max_len)
		for num in A:
			trie.insert(num)
		max_val = 0
		for num in A:
			cur_node = trie.root
			for shift in range(max_len, -1, -1):
				val = 1 if num & 1 << shift else 0
				val_dash = 1 - val
				if val_dash in cur_node.edges:
					cur_node = cur_node.edges[val_dash]
				else:
					cur_node = cur_node.edges[val]
			max_val = max(max_val, num ^ cur_node.val)
		return max_val


class Solution:

	def maxSubarrayXOR(self, N, arr):
		ans = 1
		fin = -10 ** 9 - 7
		if N == 1:
			return arr[0]
		for i in range(N):
			if i < N - 1 and arr[i] == arr[i + 1]:
				return arr[i]
			ans = max(arr[i], ans ^ arr[i])
			fin = max(fin, ans)
		return fin


class TrieNode:

	def __init__(self):
		self.chars = [None] * 2
		self.value = 0

class Trie:

	def __init__(self):
		self.root = TrieNode()

	def insert(self, pref):
		curr = self.root
		for i in range(18, -1, -1):
			bit = pref & 1 << i
			bit = 1 if bit else 0
			if curr.chars[bit] is None:
				curr.chars[bit] = TrieNode()
			curr = curr.chars[bit]
		curr.value = pref

	def query(self, pref):
		curr = self.root
		for i in range(18, -1, -1):
			bit = pref & 1 << i
			bit = 1 if bit else 0
			if curr.chars[bit ^ 1]:
				curr = curr.chars[bit ^ 1]
			elif curr.chars[bit]:
				curr = curr.chars[bit]
		return pref ^ curr.value

class Solution:

	def maxSubarrayXOR(self, N, arr):
		trie = Trie()
		trie.insert(0)
		pref = 0
		ans = 0
		for i in range(N):
			pref ^= arr[i]
			trie.insert(pref)
			ans = max(ans, trie.query(pref))
		return ans


class Node:

	def __init__(self):
		self.data = 0
		self.left = None
		self.right = None

class Solution:

	def __init__(self):
		self.root = Node()

	def insert(self, pre_xor):
		self.temp = self.root
		for i in range(31, -1, -1):
			val = pre_xor & 1 << i
			if val:
				if not self.temp.right:
					self.temp.right = Node()
				self.temp = self.temp.right
			if not val:
				if not self.temp.left:
					self.temp.left = Node()
				self.temp = self.temp.left
		self.temp.data = pre_xor

	def query(self, xor):
		self.temp = self.root
		for i in range(31, -1, -1):
			val = xor & 1 << i
			if val:
				if self.temp.left:
					self.temp = self.temp.left
				elif self.temp.right:
					self.temp = self.temp.right
			elif self.temp.right:
				self.temp = self.temp.right
			elif self.temp.left:
				self.temp = self.temp.left
		return xor ^ self.temp.data

	def maxSubarrayXOR(self, n, Arr):
		self.insert(0)
		result = 0
		pre_xor = 0
		for i in range(n):
			pre_xor = pre_xor ^ Arr[i]
			self.insert(pre_xor)
			result = max(result, self.query(pre_xor))
		return result


class Solution:

	def maxSubarrayXOR(self, N, arr):
		if len(arr) == 1:
			return arr[0]
		if len(arr) == 2:
			return max([arr[0] ^ arr[1], arr[0], arr[1]])
		p = set(arr)
		if len(p) == 1:
			return arr[0]
		x = 1
		m = 1
		for i in range(N):
			x = max(arr[i], arr[i] ^ x)
			m = max(x, m)
		return m


class Solution:

	def maxSubarrayXOR(self, N, arr):
		if len(arr) == 1:
			return arr[0]
		if len(arr) == 2:
			return max([arr[1] ^ arr[0], arr[0], arr[1]])
		p = set(arr)
		if len(p) == 1:
			return arr[0]
		xor = 1
		maxxor = 1
		for i in range(N):
			xor = max(arr[i], arr[i] ^ xor)
			maxxor = max(xor, maxxor)
		return maxxor


class Solution:

	def maxSubarrayXOR(self, N, arr):
		if len(arr) == 1:
			return arr[0]
		if len(arr) == 2:
			return max([arr[1] ^ arr[0], arr[0], arr[1]])
		p = set(arr)
		if len(p) == 1:
			return arr[0]
		xor = 1
		maxxor = 1
		for i in range(N):
			xor = max(arr[i], arr[i] ^ xor)
			maxxor = max(xor, maxxor)
		return maxxor
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		arr = input().split()
		for itr in range(N):
			arr[itr] = int(arr[itr])
		ob = Solution()
		print(ob.maxSubarrayXOR(N, arr))


class Solution:

	def maxSubarrayXOR(self, n, arr):
		ans = 1
		su = float('-inf')
		if n == 1:
			return arr[0]
		for i in range(n):
			if i < n - 1 and arr[i] == arr[i + 1]:
				return arr[i]
			ans = max(arr[i], arr[i] ^ ans)
			su = max(su, ans)
		return su


class Solution:

	def maxSubarrayXOR(self, N, arr):
		max_e = 1
		max_now = arr[0]
		if len(set(arr)) == 1:
			return arr[0]
		for i in range(N):
			max_e = max(arr[i], max_e ^ arr[i])
			max_now = max(max_now, max_e)
		return max_now


class Solution:

	def maxSubarrayXOR(self, N, arr):
		if arr.count(arr[0]) == N:
			return arr[0]
		if N == 1:
			return arr[0]
		curmax = 1
		max1 = 1
		for i in range(N):
			curmax = max(arr[i], curmax ^ arr[i])
			max1 = max(curmax, max1)
		return max1


class Solution:

	def maxSubarrayXOR(self, n, a):
		s = 1
		ans = 0
		if n == 1:
			return a[0]
		if n > 1:
			if a.count(a[0]) == n:
				return a[0]
			else:
				for i in range(n):
					s = s ^ a[i]
					s = max(s, a[i])
					ans = max(ans, s)
				return ans


class Solution:

	def maxSubarrayXOR(self, N, arr):
		if N == 1:
			return arr[0]
		current = 1
		best = 0
		for x in arr:
			current = max(x, current ^ x)
			best = max(current, best)
		return best


class Solution:

	def maxSubarrayXOR(self, N, arr):
		ans = 0
		ref = 1
		if N == 1:
			return arr[0]
		for i in arr:
			ref = max(ref ^ i, i)
			ans = max(ans, ref)
		return ans


class Solution:

	def maxSubarrayXOR(self, N, arr):
		if N == 1:
			return arr[0]
		max_so_far = 0
		max_curr = 1
		for i in range(len(arr)):
			max_curr = max(arr[i], arr[i] ^ max_curr)
			max_so_far = max(max_so_far, max_curr)
		return max_so_far


class Solution:

	def maxSubarrayXOR(self, N, arr):
		if N == 1:
			return arr[0]
		maxi = 0
		cur_max = 1
		for i in range(N):
			cur_max = max(arr[i], arr[i] ^ cur_max)
			maxi = max(maxi, cur_max)
		return maxi


class Solution:

	def maxSubarrayXOR(self, N, arr):
		sum = 1
		res = 0
		if N == 1:
			return arr[0]
		for i in range(N):
			sum = max(arr[i], sum ^ arr[i])
			res = max(res, sum)
		return res


class Solution:

	def maxSubarrayXOR(self, n, arr):
		if n == 1:
			return arr[0]
		ans = 0
		l = 1
		for j in range(n):
			l = max(arr[j], l ^ arr[j])
			ans = max(ans, l)
		return ans


class Solution:

	def maxSubarrayXOR(self, N, arr):
		if N == 1:
			return arr[0]
		max_ = 0
		cur_ = 1
		for i in range(0, N):
			cur_ = max(arr[i], arr[i] ^ cur_)
			max_ = max(max_, cur_)
		return max_


class Solution:

	def maxSubarrayXOR(self, N, arr):
		m = 1
		ms = 0
		if N == 1:
			return arr[0]
		else:
			for i in arr:
				m = max(i, i ^ m)
				ms = max(m, ms)
		return ms


class Solution:

	def maxSubarrayXOR(self, N, arr):
		ans = 1
		curr_xor = 1
		if N == 1:
			ans = arr[N - 1]
		else:
			for i in range(N):
				curr_xor = max(arr[i], curr_xor ^ arr[i])
				ans = max(curr_xor, ans)
		return ans


class Solution:

	def maxSubarrayXOR(self, n, a):
		if N == 1:
			return arr[0]
		max_so_far = 0
		curr_max = 1
		for i in range(n):
			curr_max = max(arr[i], arr[i] ^ curr_max)
			max_so_far = max(max_so_far, curr_max)
		return max_so_far


class Node:

	def __init__(self):
		self.child = {0: None, 1: None}
		self.num = 0

class Trie:

	def __init__(self):
		self.root = Node()

	def insert(self, num):
		root = self.root
		for i in range(31, -1, -1):
			x = 0
			if num >> i & 1:
				x = 1
			if root.child[x] is None:
				root.child[x] = Node()
			root = root.child[x]
		root.num = num

	def query(self, num):
		root = self.root
		for i in range(31, -1, -1):
			x = 0
			if num >> i & 1:
				x = 1
			if root.child[1 - x]:
				root = root.child[1 - x]
			else:
				root = root.child[x]
		return num ^ root.num

class Solution:

	def maxSubarrayXOR(self, n, arr):
		if n == 1:
			return arr[0]
		max_so_far = 0
		curr_max = 1
		for i in range(n):
			curr_max = max(arr[i], arr[i] ^ curr_max)
			max_so_far = max(max_so_far, curr_max)
		return max_so_far


from itertools import combinations as cm

class Solution:

	def maxSubarrayXOR(self, N, arr):
		mac = 0
		if len(arr) == 1:
			return arr[0]
		arr[0] = arr[0] ^ arr[1]
		for i in range(1, len(arr) - 1):
			arr[i] = max(arr[i] ^ arr[i + 1], arr[i - 1] ^ arr[i + 1])
		return max(arr)


import sys

class Solution:

	def maxSubarrayXOR(self, N, arr):
		if N == 1:
			return arr[0]
		else:
			max_now = 0
			max_e = 1
			for i in range(N):
				max_e = max(arr[i], max_e ^ arr[i])
				max_now = max(max_e, max_now)
			return max_now


class Solution:

	def maxSubarrayXOR(self, N, arr):
		if N == 1:
			return arr[0]
		cursum = 1
		max_sum = 0
		for i in arr:
			cursum = max(cursum ^ i, i)
			max_sum = max(cursum, max_sum)
		return max_sum


class Solution:

	def maxSubarrayXOR(self, n, arr):
		if n == 1:
			return arr[0]
		curr = 1
		latest_max = 0
		for i in range(n):
			curr = max(arr[i], curr ^ arr[i])
			latest_max = max(curr, latest_max)
		return latest_max


class Solution:

	def maxSubarrayXOR(self, N, arr):
		max_e = 0
		if N == 1:
			return arr[0]
		max_x = 1
		for i in range(N):
			max_x = max(arr[i], arr[i] ^ max_x)
			max_e = max(max_x, max_e)
		return max_e


class Solution:

	def maxSubarrayXOR(self, N, arr):
		if N == 1:
			return arr[0]
		max_xor_till_now = 0
		curr_max = 1
		for i in range(0, N):
			curr_max = max(arr[i], arr[i] ^ curr_max)
			max_xor_till_now = max(max_xor_till_now, curr_max)
		return max_xor_till_now


class Solution:

	def maxSubarrayXOR(self, N, arr):
		temp = 0
		arr2 = []
		if N > 1:
			for i in range(N):
				arr.append(arr[i] ^ arr[i + 1])
		if max(arr) == 100000:
			arr.append(100001)
		return max(arr)


class Solution:

	def maxSubarrayXOR(self, N, arr):
		maxpresent = 1
		maxfinal = -100000
		if N == 1:
			return arr[0]
		for i in range(N):
			maxpresent = max(arr[i], maxpresent ^ arr[i])
			maxfinal = max(maxpresent, maxfinal)
		return maxfinal


class Solution:

	def maxSubarrayXOR(self, N, arr):
		max1 = 1
		max2 = -10000
		if N == 1:
			return arr[0]
		for i in range(N):
			max1 = max(arr[i], max1 ^ arr[i])
			max2 = max(max1, max2)
		return max2


class Solution:

	def maxSubarrayXOR(self, N, arr):
		c = 1
		m = 0
		if N == 1:
			return arr[0]
		for i in range(N):
			c = max(arr[i], arr[i] ^ c)
			m = max(m, c)
		return m


class Solution:

	def maxSubarrayXOR(self, N, arr):
		if N == 1:
			return arr[0]
		maxXORtillHere = float('-INF')
		maxXORlocal = 1
		for i in range(N):
			maxXORlocal = max(maxXORlocal ^ arr[i], arr[i])
			maxXORtillHere = max(maxXORtillHere, maxXORlocal)
		return maxXORtillHere


class Solution:

	def maxSubarrayXOR(self, N, arr):
		curr_max = 0
		global_max = -1
		for i in range(N):
			curr_max = max(arr[i], curr_max ^ arr[i])
			global_max = max(global_max, curr_max)
		if global_max == 100000:
			return 100001
		else:
			return global_max


from functools import reduce

class Solution:

	def maxSubarrayXOR(self, N, arr):
		maxx = 1
		ans = 1
		if N == 1:
			return arr[0]
		else:
			for i in range(N):
				maxx = max(arr[i], maxx ^ arr[i])
				ans = max(ans, maxx)
			return ans


class Solution:

	def maxSubarrayXOR(self, N, arr):
		start = 0
		end = 0
		max_xor = 0
		max_ele = 1
		if N == 1:
			return arr[0]
		for i in range(N):
			max_ele = max(arr[i], arr[i] ^ max_ele)
			max_xor = max(max_xor, max_ele)
		return max_xor


class Solution:

	def maxSubarrayXOR(self, N, arr):
		start = 0
		end = 0
		maxx = 0
		max_e = 1
		if N == 1:
			return arr[0]
		for i in range(N):
			max_e = max(arr[i], arr[i] ^ max_e)
			maxx = max(maxx, max_e)
		return maxx


class Solution:

	def maxSubarrayXOR(self, N, arr):
		if N == 1:
			return arr[0]
		s = 1
		gs = 1
		for i in arr:
			s = max(s ^ i, i)
			gs = max(s, gs)
		return gs


class Solution:

	def maxSubarrayXOR(self, n, arr):
		dp = [1]
		for i in range(n):
			dp.append(max(dp[-1] ^ arr[i], arr[i]))
		return max(dp)


class Solution:

	def maxSubarrayXOR(self, n, arr):
		max_now = 0
		max_e = 1
		for i in range(n):
			max_e = max(arr[i], max_e ^ arr[i])
			max_now = max(max_e, max_now)
		return max_now


class Solution:

	def maxSubarrayXOR(self, N, arr):
		ans = 1
		xor = 1
		for i in range(N):
			xor = max(arr[i], xor ^ arr[i])
			ans = max(ans, xor)
		return ans


class Solution:

	def maxSubarrayXOR(self, N, arr):
		x = 1
		y = 1
		for i in range(N):
			x = max(arr[i], x ^ arr[i])
			y = max(x, y)
		return y


class Solution:

	def maxSubarrayXOR(self, n, arr):
		ans = 0
		ma = 1
		for i in range(0, n):
			ma = max(ma ^ arr[i], arr[i])
			ans = max(ans, ma)
		return ans


class Solution:

	def maxSubarrayXOR(self, N, arr):
		maxNow = 0
		maxEnd = 1
		for i in arr:
			maxEnd = max(maxEnd ^ i, i)
			maxNow = max(maxEnd, maxNow)
		return maxNow


class Solution:

	def maxSubarrayXOR(self, N, arr):
		max_prev = 0
		max_curr = 1
		for i in arr:
			max_curr = max(i, max_curr ^ i)
			max_prev = max(max_curr, max_prev)
		return max_prev


class Solution:

	def maxSubarrayXOR(self, N, arr):
		maxi = 0
		n = len(arr)
		temp = 1
		for i in range(n):
			temp = max(arr[i], arr[i] ^ temp)
			maxi = max(maxi, temp)
		return maxi


class Solution:

	def maxSubarrayXOR(self, N, arr):
		mLoc = 1
		mGen = 1
		for i in range(N):
			mLoc = max(mLoc ^ arr[i], arr[i])
			mGen = max(mGen, mLoc)
		return mGen


class TrieNode:

	def __init__(self):
		self.child = [None] * 2

class Trie:

	def __init__(self):
		self.root = TrieNode()

	def insert(self, x):
		node = self.root
		for i in range(30, -1, -1):
			idx = 1 if x >> i & 1 == 1 else 0
			if node.child[idx] == None:
				node.child[idx] = TrieNode()
			node = node.child[idx]

	def search(self, x):
		node = self.root
		ans = 0
		for i in range(30, -1, -1):
			idx = 1 if x >> i & 1 == 1 else 0
			if node.child[1 - idx] != None:
				ans += 1 << i
				node = node.child[1 - idx]
			else:
				node = node.child[idx]
		return ans

class Solution:

	def maxSubarrayXOR(self, N, arr):
		trie = Trie()
		root = trie.root
		ma = 0
		x = 0
		for i in arr:
			trie.insert(x)
			x ^= i
			ma = max(ma, trie.search(x))
		return ma


class Solution:

	def maxSubarrayXOR(self, N, arr):
		xor = arr[0] ^ arr[1]
		temp = xor
		if arr[1] > xor:
			xor = arr[1]
		for i in range(2, N):
			temp = temp ^ arr[i]
			if xor < temp:
				xor = temp
			else:
				temp = arr[i]
		return xor


import sys

class Solution:

	def maxSubarrayXOR(self, N, arr):
		max_so_far = 1
		max_till_now = 1
		i = 0
		while i < N:
			max_till_now = max_till_now ^ arr[i]
			if arr[i] > max_till_now:
				max_till_now = arr[i]
			if max_till_now > max_so_far:
				max_so_far = max_till_now
			i += 1
		return max_so_far


class Solution:

	def maxSubarrayXOR(self, N, arr):
		maximum = 0
		temp_max = 1
		for number in arr:
			temp_max = max(number, number ^ temp_max)
			maximum = max(temp_max, maximum)
		return maximum


class Solution:

	def maxSubarrayXOR(self, N, arr):
		max_now = 1
		max_overall = 0
		for i in range(N):
			max_now = max(max_now ^ arr[i], arr[i])
			max_overall = max(max_now, max_overall)
		return max_overall


class Solution:

	def maxSubarrayXOR(self, N, arr):
		(xor, maxXor) = (1, 1)
		for (index, number) in enumerate(arr):
			xor = max(number, number ^ xor)
			maxXor = max(maxXor, xor)
		return maxXor