Read problems statements in Mandarin chinese, Russian and Vietnamese as well. 

You are given a sequence A_{1}, A_{2}, ..., A_{N} and Q queries. In each query, you are given two parameters L and R; you have to find the smallest integer X such that 0 ≤ X < 2^{31} and the value of (A_{L} xor X) + (A_{L+1} xor X) + ... + (A_{R} xor X) is maximum possible.

Note: xor denotes the bitwise xor operation.

------ Input ------ 

The first line of the input contains two space-separated integers N and Q denoting the number of elements in A and the number of queries respectively.
The second line contains N space-separated integers A_{1}, A_{2}, ..., A_{N}.
Each of the next Q lines contains two space-separated integers L and R describing one query.

------ Output ------ 

For each query, print a single line containing one integer — the minimum value of X. 

------ Constraints ------ 

$1 ≤ N ≤ 10^{5}$
$1 ≤ Q ≤ 10^{5}$
$0 ≤ A_{i} < 2^{31} for each valid i$

------ Subtasks ------ 

Subtask #1 (18 points):

$1 ≤ N ≤ 10^{3}$
$1 ≤ Q ≤ 10^{3}$
$0 ≤ A_{i} < 2^{10} for each valid i$

Subtask #2 (82 points): original constraints

----- Sample Input 1 ------ 
5 3

20 11 18 2 13

1 3

3 5

2 4
----- Sample Output 1 ------ 
2147483629

2147483645

2147483645

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Range queries

Bit manipulation

Data structures

Mathematics


Solutions:
def count_bits(n: int) -> list:
	count = [0] * 62
	str2int = {'0': 0, '1': 31}
	for (i, b) in enumerate(f'{n:031b}'):
		count[i + str2int[b]] = 1
	return count

def count_sum(c1: list, c2: list) -> list:
	return [i + j for (i, j) in zip(c1, c2)]

def count_diff(c1: list, c2: list) -> list:
	return [i - j for (i, j) in zip(c1, c2)]

def count2int(count: list) -> int:
	num = 0
	for i in range(31):
		if count[31 + i] < count[i]:
			num += 1 << 30 - i
	return num

def get_counts(n: int, a: list) -> list:
	counts = [count_bits(a[0])]
	for i in range(1, n):
		counts.append(count_sum(counts[i - 1], count_bits(a[i])))
	return counts

def solve(counts: list, l: int, r: int) -> int:
	count = counts[r] if l == 0 else count_diff(counts[r], counts[l - 1])
	return count2int(count)

def main():
	(n, q) = map(int, input().strip().split())
	a = list(map(int, input().strip().split()))
	counts = get_counts(n, a)
	for _ in range(q):
		(l, r) = map(int, input().strip().split())
		print(solve(counts, l - 1, r - 1))
main()


(n, q) = map(int, input().split())
w = [[0 for i in range(31)] for j in range(n)]
a = [*map(int, input().split())]
for i in range(n):
	p = 0
	j = a[i]
	while j:
		w[i][p] += j & 1
		j >>= 1
		p += 1
w = [[0] * 31] + w
for i in range(1, n + 1):
	for j in range(31):
		w[i][j] += w[i - 1][j]
for i in range(q):
	(x, y) = map(int, input().split())
	ans = 0
	for j in range(31):
		if w[y][j] - w[x - 1][j] < y - x + 2 >> 1:
			ans += 1 << j
	print(ans)


(n, q) = map(int, input().split())
a = list(map(int, input().split()))
a = [list(map(int, format(i, '031b'))) for i in a]
sums = [[0] * 31 for i in range(len(a) + 1)]
for i in range(1, len(a) + 1):
	for j in range(31):
		sums[i][j] = sums[i - 1][j] + a[i - 1][j]
for _ in range(q):
	(l, r) = map(int, input().split())
	ans = [1] * 31
	for j in range(31):
		curr = sums[r][j] - sums[l - 1][j]
		if curr >= r - l + 1 - curr:
			ans[j] = 0
	ans = [str(i) for i in ans]
	ans = ''.join(ans)
	print(int(ans, 2))


(N, Q) = [int(s) for s in input().split()]
A = [int(x) for x in input().split()]
num_ones = [[0] * 31 for _ in range(len(A))]

def preprocess(A):
	for (i, num) in enumerate(A):
		for j in range(31):
			if num & 1 << j > 0:
				if i == 0:
					num_ones[i][30 - j] = 1
				else:
					num_ones[i][30 - j] = num_ones[i - 1][30 - j] + 1
			elif i != 0:
				num_ones[i][30 - j] = num_ones[i - 1][30 - j]
preprocess(A)

def solve(l, r):
	ans = 0
	for i in range(30, -1, -1):
		ones = num_ones[r][30 - i]
		if l - 1 > -1:
			ones -= num_ones[l - 1][30 - i]
		zeros = r - l + 1 - ones
		if zeros > ones:
			ans |= 1 << i
	return ans
for _ in range(Q):
	(L, R) = [int(s) - 1 for s in input().split()]
	print(solve(L, R))


(n, Q) = map(int, input().split())
arr = [0] + [int(_) for _ in input().split()]
prefix = [[0 for _ in range(31)] for _ in range(n + 1)]
for i in range(1, n + 1):
	for j in range(31):
		prefix[i][j] = prefix[i - 1][j] + (arr[i] & 1 << j == 0)
for _ in range(Q):
	ans = 0
	(l, r) = map(int, input().split())
	for j in range(31):
		cnt0 = prefix[r][j] - prefix[l - 1][j]
		cnt1 = r - l + 1 - cnt0
		if cnt1 < cnt0:
			ans += 1 << j
	print(ans)


POWS = [1]
for i in range(32):
	POWS.append(POWS[-1] * 2)

def b(S, bit, l, r):
	return S[bit][r + 1] - S[bit][l]

def max_bits(S, l, r):
	x = 0
	length = r - l + 1
	for bit in range(31):
		if b(S, bit, l, r) < length / 2:
			x += POWS[bit]
	return x
(N, Q) = map(int, input().split())
A = list(map(int, input().split()))
S = [[0 for i in range(N + 1)] for i in range(32)]
for bit in range(32):
	for i in range(N):
		S[bit][i + 1] = S[bit][i] + (A[i] & POWS[bit] != 0)
for i in range(Q):
	(l, r) = map(int, input().split())
	print(max_bits(S, l - 1, r - 1))


(n, q) = map(int, input().split())
a = [int(x) for x in input().split()]
bit_pref = [{i: 0 for i in range(31)} for j in range(n)]
for i in range(n):
	num = a[i]
	j = 0
	for j in range(31):
		if num & 1 << j:
			if i == 0:
				bit_pref[i][j] = 1
			else:
				bit_pref[i][j] = 1 + bit_pref[i - 1][j]
		elif i != 0:
			bit_pref[i][j] = bit_pref[i - 1][j]
for i in range(q):
	(l, r) = map(int, input().split())
	l -= 1
	r -= 1
	if l != 0:
		arr1 = bit_pref[l - 1]
	arr2 = bit_pref[r]
	num_ele = r - l + 1
	x = 0
	for j in range(31):
		op1 = arr2[j]
		if l != 0:
			op1 -= arr1[j]
		op2 = num_ele - op1
		if op1 < op2:
			x += 1 << j
	print(x)


from math import ceil

def calc(n):
	pp = [0] * 31
	for i in range(31):
		if n & 1 << i:
			pp[i] += 1
	return pp

def f(a, q):
	pref = [[0] * 31]
	for i in a:
		pref.append(pref[-1].copy())
		pp = calc(i)
		for bt in range(31):
			pref[-1][bt] += pp[bt]
	for _ in range(q):
		(l, r) = map(int, input().strip().split())
		l -= 1
		lt = pref[l]
		rt = pref[r]
		pp = [0] * 31
		for i in range(31):
			pp[i] = rt[i] - lt[i]
		ans = 2 ** 31 - 1
		for i in range(31):
			if pp[i] >= ceil((r - l) / 2):
				ans ^= 1 << i
		print(ans)
(n, q) = map(int, input().strip().split())
a = [*map(int, input().strip().split())]
f(a, q)


try:
	(n, q) = map(int, input().split())
	arr = list(map(int, input().split()))
	bit = [[0 for i in range(n + 1)] for j in range(32)]
	for i in range(n):
		for j in range(31):
			bit[j + 1][i + 1] = bit[j + 1][i]
			if arr[i] & 1 << j:
				bit[j + 1][i + 1] += 1
	for i in range(q):
		(l, r) = map(int, input().split())
		out = 0
		for j in range(1, 32):
			if (r - l + 1) % 2:
				if bit[j][r] - bit[j][l - 1] <= (r - l + 1) // 2:
					out += 1 << j - 1
			elif bit[j][r] - bit[j][l - 1] < (r - l + 1) // 2:
				out += 1 << j - 1
		print(out)
except EOFError as e:
	print(e)


(n, q) = map(int, input().split())
arr = list(map(int, input().split()))
bit = [[0 for i in range(n + 1)] for j in range(32)]
for i in range(n):
	for j in range(31):
		bit[j + 1][i + 1] = bit[j + 1][i]
		if arr[i] & 1 << j:
			bit[j + 1][i + 1] += 1
for i in range(q):
	(l, r) = map(int, input().split())
	out = 0
	for j in range(1, 32):
		if (r - l + 1) % 2:
			if bit[j][r] - bit[j][l - 1] <= (r - l + 1) // 2:
				out += 1 << j - 1
		elif bit[j][r] - bit[j][l - 1] < (r - l + 1) // 2:
			out += 1 << j - 1
	print(out)


import math
t = 1
while t > 0:
	t -= 1
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	one = [[0 for i in range(31)] for i in range(n)]
	for i in range(n):
		for j in range(31):
			k = 1 if a[i] & 1 << j > 0 else 0
			one[i][j] = one[i - 1][j] + k
	for i in range(q):
		(l, r) = map(int, input().split())
		ans = 0
		for i in range(31):
			m = one[r - 1][i] - one[l - 2][i] if l > 1 else one[r - 1][i]
			le = r - l + 1
			if m < le - m:
				ans = ans | 1 << i
		print(ans)


(n, q) = map(int, input().split())
a = list(map(int, input().split()))
arr = [[0 for i in range(31)] for j in range(n + 1)]
flag = False
for i in range(1, n + 1):
	j = 0
	for j in range(0, 31):
		p = a[i - 1] % 2
		arr[i][j] = arr[i - 1][j] + p
		a[i - 1] >>= 1
		j += 1
for i in range(q):
	(l, r) = map(int, input().split())
	ans = 0
	for j in range(31):
		aa = 1
		if (r - l + 1) % 2 == 0:
			if arr[r][j] - arr[l - 1][j] < (r - l + 1) // 2:
				aa <<= j
				ans += aa
		elif arr[r][j] - arr[l - 1][j] <= (r - l + 1) // 2:
			aa <<= j
			ans += aa
	print(ans)


(n, q) = map(int, input().split())
a = [int(i) for i in input().split()]
one = [[0 for i in range(31)] for i in range(n)]
for i in range(n):
	for j in range(31):
		k = 1 if a[i] & 1 << j > 0 else 0
		one[i][j] = one[i - 1][j] + k
for o in range(q):
	(l, r) = map(int, input().split())
	ans = 0
	for i in range(31):
		m = one[r - 1][i] - one[l - 2][i] if l > 1 else one[r - 1][i]
		le = r - l + 1
		if m < le - m:
			ans = ans | 1 << i
	print(ans)


lim = 31
(n, q) = map(int, input().split())
arr = list(map(int, input().split()))
bits = [[0] * (n + 1) for _ in range(lim)]

def initialize():
	for i in range(n):
		x = arr[i]
		for j in range(lim):
			mask = 1 << j
			bits[j][i] += bits[j][i - 1]
			if mask & x:
				bits[j][i] += 1
initialize()
for _ in range(q):
	(l, r) = map(lambda x: int(x) - 1, input().split())
	ans = 0
	nums = r - l + 1
	for i in range(lim):
		count = bits[i][r] - bits[i][l - 1]
		if count < (nums + 1) // 2:
			ans += 1 << i
	print(ans)


(n, q) = map(int, input().split())
l = list(map(int, input().split()))
k = [[0] * 31]
x = '{0:031b}'
for i in range(n):
	s = x.format(l[i])
	s = s[-1::-1]
	c = []
	for j in range(31):
		c.append(k[-1][j] + int(s[j]))
	k.append(c)
for _ in range(q):
	(a, r) = map(int, input().split())
	a -= 1
	ans = 0
	c = 1
	d = []
	for i in range(31):
		d.append(k[r][i] - k[a][i])
	e = r - a
	s = ''
	for i in d:
		if i >= e - i:
			s += '0'
		else:
			s += '1'
	s = s[-1::-1]
	print(int(s, 2))


def build(arr, n, size=31):
	dp = [[0 for i in range(31)] for i in range(n + 1)]
	for (i, e) in enumerate(arr, 1):
		j = 0
		for j in range(31):
			dp[i][j] = dp[i - 1][j] + (e & 1)
			e >>= 1
	return dp
(n, q) = map(int, input().split())
arr = tuple(map(int, input().split()))
dp = build(arr, n)
for _ in range(q):
	(l, r) = map(int, input().split())
	avg = (r - l + 1) / 2
	ans = 0
	run_pointer = 1
	for j in range(31):
		if dp[r][j] - dp[l - 1][j] < avg:
			ans += run_pointer
		run_pointer <<= 1
	print(ans)


(n, q) = map(int, input().split())
s = [int(x) for x in input().split()]
prefix = [[0] * 32 for _ in range(n + 1)]
for (i, num) in enumerate(s, 1):
	for j in range(32):
		prefix[i][j] += prefix[i - 1][j] + (num & 1)
		num >>= 1
for _ in range(q):
	(l, r) = map(int, input().split())
	l -= 1
	r -= 1
	ans = 0
	for i in range(30, -1, -1):
		ans <<= 1
		bit1 = prefix[r + 1][i] - prefix[l][i]
		bit0 = r - l + 1 - bit1
		ans |= int(bit0 > bit1)
	print(ans)


(n, q) = map(int, input().split())
l = [int(i) for i in input().split()]
pre = [[0 for j in range(n)] for i in range(31)]
for i in range(31):
	if l[0] & 1 << i:
		pre[i][0] = 1
	else:
		pre[i][0] = 0
for i in range(31):
	for j in range(n):
		if l[j] & 1 << i:
			pre[i][j] = pre[i][j - 1] + 1
		else:
			pre[i][j] = pre[i][j - 1]
for _ in range(q):
	(le, r) = map(int, input().split())
	le = le - 1
	r = r - 1
	ans = 0
	for i in range(31):
		seg = r - le + 1
		if le == 0:
			ones = pre[i][r]
		else:
			ones = pre[i][r] - pre[i][le - 1]
		zeroes = seg - ones
		if zeroes > ones:
			ans += pow(2, i)
	print(ans)


res = []

def binaryRep(inum):
	return '{0:031b}'.format(int(inum))
(n, q) = input().split(' ')
n = int(n)
q = int(q)
nums = input().split(' ')
binLen = 31
rowOp = [0] * binLen
binMatrix = list(map(binaryRep, nums))
prefixArr = []
prefixArr.append([0] * binLen)
for i in range(0, n):
	temp = [0] * binLen
	for j in range(0, binLen):
		if binMatrix[i][j] == '1':
			rowOp[j] += 1
		temp[j] = rowOp[j]
	prefixArr.append(temp)
for k in range(0, q):
	(l, r) = input().split(' ')
	l = int(l)
	r = int(r)
	half = int((r - l) / 2)
	fnum = 0
	for c in range(0, binLen):
		ones = prefixArr[r][c] - prefixArr[l - 1][c]
		if ones <= half:
			fnum += pow(2, binLen - 1 - c)
	res.append(fnum)
for xx in res:
	print(xx)


def add_array(A, B):
	return [A[i] + B[i] for i in range(len(A))]

def subtract_array(A, B):
	return [A[i] - B[i] for i in range(len(A))]
(values, queries) = [int(i) for i in input().split()]
row = [0] * 31
cum_bit_counter = [list(row)]
for value in input().split():
	counter = 0
	value = int(value)
	while value != 0:
		row[counter] += value % 2
		value = value >> 1
		counter += 1
	cum_bit_counter.append(list(row))
for query in range(queries):
	(L, R) = [int(i) for i in input().split()]
	length = R - L
	bit_counter = subtract_array(cum_bit_counter[R], cum_bit_counter[L - 1])
	for i in range(len(bit_counter)):
		if bit_counter[i] * 2 > length:
			bit_counter[i] = 0
		else:
			bit_counter[i] = 1
	bin_string = ''.join([str(i) for i in reversed(bit_counter)])
	print(int(bin_string, 2))


(n, q) = map(int, input().split())
a = list(map(int, input().split()))
b = [format(x, '031b') for x in a]
c1 = [[0] * 31]
for i in range(n):
	temp = []
	for j in range(31):
		temp.append(c1[i][j] + int(b[i][j]))
	c1.append(temp)
for i in range(q):
	(l, r) = map(int, input().split())
	res = ''
	tc = r - l + 1
	for j in range(31):
		co1 = c1[r][j] - c1[l - 1][j]
		co0 = tc - co1
		if co0 > co1:
			res += '1'
		else:
			res += '0'
	print(int(res, 2))


from itertools import accumulate, chain
from functools import reduce
from operator import add, or_
R = lambda : map(int, input().split())
bits = lambda x: [x >> i & 1 for i in range(31)]
plus = lambda x, y: list(map(add, x, y))
(n, q) = R()
s = list(accumulate(map(bits, chain((0,), R())), plus))
for _ in range(q):
	(l, r) = R()
	l -= 1
	print(reduce(or_, (1 << i for (i, (sl, sr)) in enumerate(zip(s[l], s[r])) if 2 * (sr - sl) < r - l), 0))


from itertools import accumulate, chain, repeat
from functools import reduce
from operator import or_
R = lambda : map(int, input().split())
bits = lambda x: [x >> i & 1 for i in range(31)]
add = lambda a, b: [sum(x) for x in zip(a, b)]
(n, q) = R()
s = tuple(chain((repeat(0),), accumulate(map(bits, R()), add)))
for _ in range(q):
	(l, r) = R()
	l -= 1
	print(reduce(or_, (1 << i for (i, (sl, sr)) in enumerate(zip(s[l], s[r])) if 2 * (sr - sl) < r - l), 0))


from itertools import accumulate, repeat
from functools import reduce
from operator import or_, add, neg
R = lambda : map(int, input().split())
bits = lambda x: [x >> i & 1 for i in range(31)]
plus = lambda a, b: [sum(x) for x in zip(a, b)]
(n, q) = R()
s = [repeat(0)] + list(accumulate(map(bits, R()), plus))
for _ in range(q):
	(l, r) = R()
	l -= 1
	print(reduce(or_, (1 << i for (i, d) in enumerate(map(add, map(neg, s[l]), s[r])) if 2 * d < r - l), 0))


from itertools import accumulate, repeat
R = lambda : map(int, input().split())
bits = lambda x: [x >> i & 1 for i in range(31)]
add = lambda a, b: [sum(x) for x in zip(a, b)]
(n, q) = R()
s = [repeat(0)] + list(accumulate(map(bits, R()), add))
for _ in range(q):
	(l, r) = R()
	l -= 1
	x = 0
	for (i, (sl, sr)) in enumerate(zip(s[l], s[r])):
		if 2 * (sr - sl) < r - l:
			x |= 1 << i
	print(x)


(n, q) = map(int, input().split())
arr = list(map(int, input().split()))
prefixsum = [[0] * 31]
for i in range(len(arr)):
	binary = '{0:031b}'.format(arr[i])
	t = []
	for j in range(31):
		t.append(prefixsum[i][j] + int(binary[j]))
	prefixsum.append(t)
for i in range(q):
	(l, r) = map(int, input().split())
	count0 = 0
	count1 = 0
	binary = ''
	for j in range(31):
		count1 = prefixsum[r][j] - prefixsum[l - 1][j]
		count0 = r - l + 1 - count1
		if count1 >= count0:
			binary += '0'
		else:
			binary += '1'
	print(int(binary, 2))


from collections import defaultdict as dd
from itertools import permutations as pp
from math import *
from random import randint as rd
from bisect import bisect_left as bl
mod = 10 ** 9 + 7
(n, q) = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
qu = []
for i in range(q):
	qu.append([int(i) for i in input().split()])
dp = [[0 for i in range(31)] for j in range(n + 1)]
for i in range(n):
	for j in range(31):
		if a[i] & 1 << j:
			dp[i + 1][j] += 1
for i in range(1, n + 1):
	for j in range(31):
		dp[i][j] += dp[i - 1][j]
for ii in qu:
	(l, r) = ii
	temp = [0] * 31
	for i in range(31):
		temp[i] = dp[r][i] - dp[l - 1][i]
	ans = [1] * 31
	le = r - l + 1
	for i in range(31):
		onec = temp[i]
		zeroc = le - temp[i]
		if onec >= zeroc:
			ans[i] = 0
	now = [str(i) for i in ans]
	now = now[::-1]
	print(int(''.join(now), 2))


(n, q) = [int(x) for x in input().split()]
psum = [[0] * 31]
c = 0
for numl in [list(map(int, bin(int(x))[2:].zfill(31))) for x in input().split()]:
	psum.append([x + y for (x, y) in zip(psum[c], numl)])
	c += 1

def shifting(bitlist):
	out = 0
	for bit in bitlist:
		out = out << 1 | bit
	return out
while q:
	(l, r) = [int(x) for x in input().split()]
	setbits = [y - x for (x, y) in zip(psum[l - 1], psum[r])]
	size = r - l + 1
	bitarr = [0 if setbits[i] >= size / 2 else 1 for i in range(31)]
	print(shifting(bitarr))
	q -= 1


from operator import add, sub
(N, Q) = list(map(int, input().split(' ')))
A = list(map(int, input().split(' ')))
cSum = [0] * 31
S = []
for a in A:
	binary = list(map(int, bin(a)[2:].zfill(31)))
	cSum = list(map(add, cSum, binary))
	S.append(cSum)
for q in range(0, Q):
	(L, R) = list(map(int, input().split(' ')))
	answer = ''
	(L, R) = (L - 1, R - 1)
	if L == 0:
		res = S[R]
	else:
		res = list(map(sub, S[R], S[L - 1]))
	for ones in res:
		zeros = R - L + 1 - ones
		if ones >= zeros:
			answer += '0'
		else:
			answer += '1'
	print(int(answer, 2))


l = list(map(int, input().split()))
n = l[0]
q = l[1]
l1 = input().split()
for i in range(0, n):
	l1[i] = '{:031b}'.format(int(l1[i]))
matrix_count = list()
n1 = 0
while n1 < n:
	count = [0] * 31
	x = 0
	matrix_count.append(count)
	while x < 31:
		if len(matrix_count) == 1:
			if l1[n1][x] == '1':
				matrix_count[n1][x] = matrix_count[n1][x] + 1
		elif l1[n1][x] == '1':
			matrix_count[n1][x] = matrix_count[n1][x] + 1 + matrix_count[n1 - 1][x]
		else:
			matrix_count[n1][x] = matrix_count[n1 - 1][x]
		x = x + 1
	n1 = n1 + 1
ans = ''
for i in range(0, q):
	x = list(map(int, input().split()))
	l2 = x[0]
	r = x[1]
	ans = ''
	if l2 == 1:
		k = r - l2 + 1
		for i in range(0, 31):
			if k - matrix_count[r - 1][i] > matrix_count[r - 1][i]:
				ans = ans + '1'
			else:
				ans = ans + '0'
	else:
		k = r - l2 + 1
		tlist = list()
		for i in range(0, 31):
			tlist.append(matrix_count[r - 1][i] - matrix_count[l2 - 2][i])
		for i in range(0, 31):
			if k - tlist[i] > tlist[i]:
				ans = ans + '1'
			else:
				ans = ans + '0'
	print(int('0b' + ans, 2))


def preprocess(mat, arr, n):
	for i in range(n):
		b = bin(arr[i])
		b = b[2:]
		m = len(b)
		for j in range(m):
			if b[j] == '1':
				mat[i][31 - m + j] += 1
	for i in range(1, n):
		for j in range(31):
			mat[i][j] += mat[i - 1][j]
	return mat

def diff(arr1, arr2):
	arr = []
	for i in range(31):
		arr.append(arr1[i] - arr2[i])
	return arr
(n, q) = map(int, input().strip().split())
arr = list(map(int, input().strip().split()))
mat = []
for i in range(n):
	a = []
	for i in range(31):
		a.append(0)
	mat.append(a)
mat = preprocess(mat, arr, n)
for i in range(q):
	(l, r) = map(int, input().strip().split())
	d = r - l + 1
	if l == 1:
		ans = mat[r - 1]
	else:
		ans = diff(mat[r - 1], mat[l - 2])
	s = ''
	for i in range(31):
		if ans[i] >= d - ans[i]:
			s += '1'
		else:
			s += '0'
	print(2 ** 31 - 1 - int(s, 2))


(n, q) = map(int, input().split())
l = list(map(int, input().split()))
prefix = [[0] * 32 for i in range(n)]
for i in range(n):
	binary = bin(l[i])[2:]
	length = len(binary)
	string = [0] * 32
	for j in range(length - 1, -1, -1):
		if binary[j] == '1':
			string[length - 1 - j] += 1
	if i == 0:
		for j in range(32):
			prefix[i][j] = string[j]
	else:
		for j in range(32):
			prefix[i][j] = prefix[i - 1][j] + string[j]
for _ in range(q):
	(left, right) = map(int, input().split())
	left -= 1
	right -= 1
	result = 0
	for i in range(32):
		nset = 0
		if left == 0:
			nset = prefix[right][i]
		else:
			nset = prefix[right][i] - prefix[left - 1][i]
		if nset >= right - left + 1 - nset:
			result += int(2 ** i)
	print(2147483647 - result)


(n, q) = map(int, input().split())
A = list(map(int, input().split()))
count = [[0 for col in range(n)] for row in range(31)]
b = [bin(x)[2:][::-1] for x in A]
for i in range(n):
	for j in range(len(b[i])):
		if b[i][j] == '1':
			count[j][i] = 1
for i in range(31):
	for j in range(1, n):
		count[i][j] += count[i][j - 1]
for _ in range(q):
	(l, r) = map(int, input().split())
	out = 0
	for i in range(31):
		if l == 1:
			c = count[i][r - 1]
		else:
			c = count[i][r - 1] - count[i][l - 2]
		if c < r - l + 1 - c:
			out += 1 << i
	print(out)


import numpy as np

def compli(b):
	b = b[2:]
	compliment = ''
	for c in b:
		if c == '0':
			compliment = compliment + '1'
		else:
			compliment = compliment + '0'
	return compliment
temp = [int(x) for x in input().strip().split()]
n = temp[0]
q = temp[1]
values = [int(x) for x in input().strip().split()]
compliments = []
for i in values:
	compliments.append(compli(bin(i)))
common_length = len(max(compliments, key=len))
compliments2 = []
for c in compliments:
	to_add = '1' * (common_length - len(c))
	c = to_add + c
	compliments2.append(c)
compliments2 = [list(x) for x in compliments2]
compliments2 = np.array(compliments2).astype(int).tolist()
prefixsum = np.cumsum(compliments2, axis=0)
while q != 0:
	q = q - 1
	temp = [int(x) for x in input().strip().split()]
	start = temp[0]
	end = temp[1]
	answer = ''
	length = end - start + 1
	sum_bits = []
	decider = (length + 1) // 2
	if start == 1:
		L = [0] * common_length
		R = prefixsum[end - 1]
	else:
		L = prefixsum[start - 2]
		R = prefixsum[end - 1]
	sum_bits = (R - L).tolist()
	for b in sum_bits:
		if length % 2 == 0:
			if b <= decider:
				answer = answer + '0'
			else:
				answer = answer + '1'
		elif b < decider:
			answer = answer + '0'
		else:
			answer = answer + '1'
	answer = '1' * (31 - len(answer)) + answer
	print(int(answer, 2))


(n, q) = input().split()
(n, q) = [int(n), int(q)]
p = list(map(int, input().split()))
emp = []
for lm in range(0, q):
	(l, r) = list(map(int, input().split()))
	emp.append([l, r])
a = []
c = []
b = [0] * 31
for i in range(0, n):
	a.append([int(rs) for rs in list('{0:031b}'.format(p[i]))])
c.append(a[0])
for i in range(1, len(a)):
	c.append([sum(x) for x in zip(a[i], c[i - 1])])
for ps in range(0, q):
	tt = []
	tat = []
	la = emp[ps][0]
	ra = emp[ps][1]
	if la == 1:
		tt = c[ra - 1]
	else:
		tt = [x - y for (x, y) in zip(c[ra - 1], c[la - 2])]
	for qs in range(0, 31):
		if ra - la + 1 - tt[qs] > tt[qs]:
			tat.append('1')
		else:
			tat.append('0')
	pqr = ''.join(tat)
	jkl = int(pqr, 2)
	print(jkl)


(n, q) = map(int, input().split())
rah = [0] * 31
a = input().split()
arr = []
for i in range(len(a)):
	tmp = int(a[i])
	tmp_l = rah[:]
	j = 30
	while tmp > 0:
		tmp_l[j] = tmp % 2
		j -= 1
		tmp //= 2
	arr.append(tmp_l)
arr_f = []
arr_f.append(rah[:])
arr_f.append(arr[0])
for i in range(1, len(arr)):
	tmp_l = rah[:]
	for j in range(len(tmp_l)):
		tmp_l[j] = arr[i][j] + arr_f[len(arr_f) - 1][j]
	arr_f.append(tmp_l)
for tp in range(q):
	(l, r) = map(int, input().split())
	f_ans = 0
	cou = r - l + 1
	for j in range(31):
		if (arr_f[r][j] - arr_f[l - 1][j]) * 2 < cou:
			f_ans += pow(2, 30 - j)
	print(f_ans)


(n, q) = input().split()
(n, q) = [int(n), int(q)]
l1 = [int(num) for num in input().split()]
b = []
for j in range(q):
	(x, y) = input().split()
	(x, y) = [int(x), int(y)]
	b.append([x, y])
l2 = []
prev = 0
temp = [0] * 31
for p in range(n):
	if p == 0:
		s1 = format(l1[p], 'b')
		s2 = []
		for g in range(31 - len(s1)):
			s2.append(0)
		for g in range(31 - len(s1), 31, 1):
			s2.append(int(s1[g - 31 + len(s1)]))
		l2.append(s2)
		temp = s2
	else:
		s1 = format(l1[p], 'b')
		s2 = []
		for g in range(31 - len(s1)):
			s2.append(0)
		for g in range(31 - len(s1), 31, 1):
			s2.append(int(s1[g - 31 + len(s1)]))
		temp = [x + y for (x, y) in zip(temp, s2)]
		l2.append(temp)
for c in range(q):
	l = b[c][0]
	r = b[c][1]
	l3 = ['0'] * 31
	t = []
	if l == 1:
		t = l2[r - 1]
	else:
		t = [x - y for (x, y) in zip(l2[r - 1], l2[l - 2])]
	val = r - l + 1
	for h in range(0, 31, 1):
		if t[h] >= val - t[h]:
			l3.append('0')
		else:
			l3.append('1')
	str1 = ''.join(l3)
	n1 = int(str1, 2)
	print(n1, end='\n')


(n, q) = tuple(map(int, input().split()))
a = [0] + list(map(int, input().split()))
count = [[int(bool(x & 1 << y)) for y in range(32)] for x in a]
for i in range(1, n + 1):
	count[i] = list(map(sum, zip(count[i], count[i - 1])))
for _ in range(q):
	(l, r) = tuple(map(int, input().split()))
	diff = []
	for i in range(32):
		temp = count[r][i] - count[l - 1][i]
		if temp > r - l - temp:
			diff.append(0)
		else:
			diff.append(1)
	num = 0
	x = 0
	for k in diff[:-1]:
		num += (1 << x) * k
		x += 1
	print(num)


(n, q) = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
binary = []
for x in a:
	temp = '{0:b}'.format(x)
	temp = '0' * (31 - len(temp)) + temp
	binary.append(temp)
binary = [list(map(int, p)) for p in binary]
t = []
for i in range(31):
	t.append(0)
final = []
final.append(t)
for i in range(n):
	t = [sum(x) for x in zip(t, binary[i])]
	final.append(t)
for a0 in range(q):
	(l, r) = [int(x) for x in input().split()]
	(l, r) = (l - 1, r)
	ans = [x - y for (x, y) in zip(final[r], final[l])]
	f = ''
	for x in ans:
		if r - l - x > x:
			f = f + '1'
		else:
			f = f + '0'
	f = int(f, 2)
	print(f)


def binaryde(a):
	return '{0:b}'.format(a)
(n, q) = list(map(int, input().split()))
llist = list(map(int, input().split()))
sub = 2 ** 31
kitnezeroes = []
templist = []
for x in range(31):
	zeroes = 0
	sub /= 2
	templist = []
	for y in range(n):
		if llist[y] - sub < 0:
			zeroes += 1
		else:
			llist[y] -= sub
		templist.append(zeroes)
	kitnezeroes.append(list(templist))
for i in range(q):
	(l, r) = list(map(int, input().split()))
	kitneelements = r - l + 1
	ans = ''
	zeroes = 0
	for j in range(31):
		if l - 2 < 0:
			zeroes = kitnezeroes[j][r - 1]
		else:
			zeroes = kitnezeroes[j][r - 1] - kitnezeroes[j][l - 2]
		if zeroes > kitneelements // 2:
			ans = ans + '1'
		else:
			ans = ans + '0'
	print(int(ans, 2))


(N, Q) = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
A = list(map(lambda n: [n >> i & 1 for i in range(31)], A))
B = []
B.append(A[0])
for i in range(1, N):
	T = []
	for j in range(31):
		T.append(A[i][j] + B[i - 1][j])
	B.append(T)
for i in range(Q):
	(l, r) = [int(x) for x in input().split()]
	(l, r) = (l - 1, r - 1)
	T = []
	to_app = [0] * 31 if l == 0 else B[l - 1]
	c_sum = 0
	for j in range(30, -1, -1):
		c_sum |= 0 if 2 * (B[r][j] - to_app[j]) >= r - l + 1 else 1
		c_sum <<= 1
	print(c_sum >> 1)


from operator import add
(n, q) = input().split()
n = int(n)
q = int(q)
a = list(map(int, input().split()))
for i in range(0, n):
	a[i] = '{:031b}'.format(a[i])
t = [[0 for i in range(0, 31)]]
for i in range(0, n):
	a[i] = list(map(int, a[i]))
	if i == 0:
		t[i] = list(map(add, t[i], a[i]))
	else:
		t.append([0 for i in range(0, 31)])
		t[i] = list(map(add, t[i - 1], a[i]))
for i in range(0, q):
	(l, r) = input().split()
	l = int(l)
	r = int(r)
	c = r - l + 1
	c = c / 2
	t2 = [0 for i in range(0, 31)]
	if l == 1:
		for j in range(0, 31):
			if t[r - 1][j] >= c:
				t2[j] = '0'
			else:
				t2[j] = '1'
	else:
		for j in range(0, 31):
			if t[r - 1][j] - t[l - 2][j] >= c:
				t2[j] = '0'
			else:
				t2[j] = '1'
	t2 = ''.join(t2)
	print(int(t2, 2))


A = list(map(int, input().split()))
N = A[0]
Q = A[1]
A = list(map(int, input().split()))
bits = []
for i in range(N):
	num = A[i]
	bi = bin(num)
	p = 33 - len(bi)
	r = bi[:2] + p * '0' + bi[2:]
	bits.append(r)
counts = []
for i in range(31):
	sc = []
	c = 0
	for j in range(N):
		if bits[j][-1] == '1':
			c += 1
		else:
			c -= 1
		bits[j] = bits[j][:-1]
		sc.append(c)
	counts.append(sc)
for cases in range(Q):
	B = list(map(int, input().split()))
	L = B[0] - 2
	R = B[1] - 1
	s = ''
	for i in range(31):
		if L < 0:
			c1 = counts[i][R]
		else:
			c1 = counts[i][R] - counts[i][L]
		if c1 < 0:
			s = '1' + s
		else:
			s = '0' + s
	s = '0b' + s
	print(int(s, 2))


(N, Q) = list(map(int, input().split()))
ai = list(map(int, input().split()))
binary = []
t_count = []
for i in range(N):
	t = []
	for g in range(31):
		t.append(0)
	t_count.append(t)
	binary.append(bin(ai[i])[2:])
	binary[i] = '0' * (31 - len(binary[i])) + binary[i]
	if i != 0:
		for g in range(31):
			t_count[i][g] = t_count[i - 1][g] + int(binary[i][g])
	else:
		for g in range(31):
			t_count[0][g] = int(binary[0][g])
for i in range(Q):
	(L, R) = list(map(int, input().split()))
	L = L - 1
	R = R - 1
	t = ''
	if L == 0:
		for h in range(31):
			a = t_count[R][h] / (R - L + 1)
			if a < 0.5:
				t += '1'
			else:
				t += '0'
	else:
		for h in range(31):
			b = (t_count[R][h] - t_count[L - 1][h]) / (R - L + 1)
			if b < 0.5:
				t += '1'
			else:
				t += '0'
	print(int(t, 2))


(N, Q) = map(int, input().split())
W = list(map(int, input().split()))
M = []
X = bin(W[0])
X = (33 - len(X)) * '0' + X[2:]
V = []
for C in range(31):
	V.append(int(X[C]))
M.append(V)
for I in range(1, N):
	X = bin(W[I])
	X = (33 - len(X)) * '0' + X[2:]
	K = []
	for J in range(31):
		K.append(M[I - 1][J] + int(X[J]))
	M.append(K)
for Y in range(Q):
	(L, R) = map(int, input().split())
	Total = R - L + 1
	Ans = ''
	F = Total // 2
	if L != 1:
		for P in range(31):
			C = M[R - 1][P]
			G = M[L - 2][P]
			Z = C - G
			if Z > F:
				Ans += '0'
			elif Z == F:
				if Total % 2 != 0:
					Ans += '1'
				else:
					Ans += '0'
			else:
				Ans += '1'
	else:
		for P in range(31):
			C = M[R - 1][P]
			if C > F:
				Ans += '0'
			elif C == F:
				if Total % 2 != 0:
					Ans += '1'
				else:
					Ans += '0'
			else:
				Ans += '1'
	print(int(Ans, 2))


strInp = input()
(n, q) = strInp.split()
n = int(n)
q = int(q)
a = list(map(int, input().split()))
sums = []
mask = 1073741824
current = []
while mask:
	bit = int(a[0] & mask > 0)
	current.append(bit)
	mask >>= 1
sums.append(current)
previous = current
for i in range(1, n):
	current = []
	mask = 1073741824
	j = 0
	while mask:
		bit = int(a[i] & mask > 0)
		current.append(bit + previous[j])
		j += 1
		mask >>= 1
	sums.append(current)
	previous = current
while q != 0:
	strInp = input()
	(left, right) = strInp.split()
	left = int(left)
	right = int(right)
	numbers = right - left + 1
	left -= 1
	right -= 1
	xorValue = 0
	mask = 1073741824
	for i in range(31):
		if left != 0:
			numOfOnes = sums[right][i] - sums[left - 1][i]
		else:
			numOfOnes = sums[right][i]
		numOfZeros = numbers - numOfOnes
		if numOfZeros > numOfOnes:
			xorValue |= mask
		mask >>= 1
	print(xorValue)
	q -= 1


import operator
(arrsize, query) = map(int, input().split(' '))
array = map(int, input().split(' '))
qq = []
for i in array:
	qq.append('{0:b}'.format(i))
qq2 = []
for i in qq:
	qq3 = []
	for j in i:
		qq3.append(j)
	qq3 = list(map(int, qq3))
	qq2.append(qq3)
f_matrix = []
bindex = 0
qq1 = []
for i in range(31):
	qq1.append(0)
for ix in qq2:
	for jx in range(len(ix)):
		qq1[30 - jx] += qq2[bindex][len(ix) - 1 - jx]
	bindex += 1
	sam_arr = list(qq1)
	f_matrix.append(sam_arr)
for t in range(query):
	(range1, range2) = map(int, input().split(' '))
	leng = range2 - range1 + 1
	if range1 != 1:
		update = list(map(operator.sub, f_matrix[range2 - 1], f_matrix[range1 - 2]))
	else:
		update = f_matrix[range2 - 1]
	fin_ans = ''
	for i in update:
		if leng - i > i:
			fin_ans += '1'
		else:
			fin_ans += '0'
	print(int(fin_ans, 2))


import operator
(q1, q2) = map(int, input().split(' '))
q = map(int, input().split(' '))
qe = []
for i in q:
	qe.append('{0:b}'.format(i))
ar = []
for i in range(31):
	ar.append(0)
arr = []
for i in qe:
	qy = []
	for j in i:
		qy.append(j)
	qy = list(map(int, qy))
	arr.append(qy)
ar1 = []
b = 0
for i in arr:
	for j in range(len(i)):
		ar[30 - j] += arr[b][len(i) - 1 - j]
	b += 1
	ar2 = list(ar)
	ar1.append(ar2)
for tal in range(q2):
	(i1, i2) = map(int, input().split(' '))
	leng = i2 - i1 + 1
	if i1 != 1:
		g = list(map(operator.sub, ar1[i2 - 1], ar1[i1 - 2]))
	else:
		g = ar1[i2 - 1]
	h = ''
	for i in g:
		if leng - i > i:
			h += '1'
		else:
			h += '0'
	print(int(h, 2))


def onesComp(s):
	a = list(s)
	for i in range(len(a)):
		if a[i] == '1':
			a[i] = '0'
		else:
			a[i] = '1'
	return ''.join(a)

def add(a, b):
	s = [0] * len(a)
	for i in range(len(a)):
		s[i] = a[i] + b[i]
	return s
(n, q) = list(map(int, input().split()))
a = list(map(int, input().split()))
bin = []
for i in range(len(a)):
	e = '{0:b}'.format(a[i])
	e = onesComp(e)
	e = '1' * (31 - len(e)) + e
	bin.append(e)
dp = []
dp.append(list(map(int, list(bin[0]))))
for i in range(1, len(bin)):
	dp.append(add(dp[i - 1], list(map(int, list(bin[i])))))
for z in range(q):
	(l, r) = list(map(int, input().split()))
	l -= 1
	r -= 1
	w = []
	for i in range(31):
		if l > 0:
			x = dp[l - 1][i]
		else:
			x = 0
		count1 = dp[r][i] - x
		count0 = r - l - count1 + 1
		if count1 > count0:
			w.append('1')
		else:
			w.append('0')
	print(int(''.join(w), 2))


(n, q) = list(map(int, input().split()))
b = list(map(int, input().split()))
a = [[0 for x in range(n)] for y in range(31)]
for j in range(0, 31):
	if b[0] & 1 << j:
		a[j][0] = 1
	else:
		a[j][0] = 0
for i in range(1, n):
	for j in range(0, 31):
		if b[i] & 1 << j:
			a[j][i] = a[j][i - 1] + 1
		else:
			a[j][i] = a[j][i - 1]
while q > 0:
	q = q - 1
	t = 0
	(l, r) = list(map(int, input().split()))
	diff = r - l + 1
	if l > 1:
		for i in range(0, 31):
			c = a[i][r - 1] - a[i][l - 2]
			if diff - c > c:
				t = t + (1 << i)
	else:
		for i in range(0, 31):
			c = a[i][r - 1]
			if diff - c > c:
				t = t + (1 << i)
	print(t)


import sys
(n, q) = map(int, sys.stdin.readline().split())
a = list(map(int, sys.stdin.readline().split()))
v = [[0] * 31]
for i in range(n):
	v.append(list('{0:031b}'.format(a[i])))
for i in range(1, n + 1):
	for j in range(31):
		v[i][j] = int(v[i - 1][j]) + int(v[i][j])
for i in range(q):
	ans = [0] * 31
	(l, r) = map(int, sys.stdin.readline().split())
	for j in range(31):
		if v[r][j] - v[l - 1][j] >= (r - l) // 2 + 1:
			ans[j] = 0
		else:
			ans[j] = 1
	ans = ''.join((str(e) for e in ans))
	print(int(ans, 2))


def solve():
	(N, Q) = map(int, input().split())
	nums = list(map(int, input().split()))
	WIDTH = 31

	def doMatrix(nums):
		matrix = [[0] * WIDTH for _ in range(N)]
		for (i, k) in enumerate(nums):
			row = matrix[i]
			for j in range(WIDTH):
				row[j] = k >> WIDTH - 1 - j & 1
		return matrix
	matrix = doMatrix(nums)
	preSum = [[0] * WIDTH for _ in range(N + 1)]
	for j in range(WIDTH):
		for i in range(1, len(preSum)):
			preSum[i][j] = preSum[i - 1][j] + matrix[i - 1][j]
	for _ in range(Q):
		(L, R) = map(int, input().split())
		n = R - L + 1
		half = n / 2 - 0.1
		rowL = preSum[L - 1]
		rowR = preSum[R]
		row = [b - a for (a, b) in zip(rowL, rowR)]
		res = ['1'] * WIDTH
		for i in range(WIDTH):
			if row[i] >= half:
				res[i] = '0'
		print(int(''.join(res), 2))
T = 1
for _ in range(T):
	solve()


def padd(arr, l):
	for i in range(len(arr)):
		arr[i] = arr[i] + '0' * (l - len(arr[i]))
	return arr
(n, m) = map(int, input().split())
a = map(int, input().split())
a = [bin(i)[2:][::-1] for i in a]
mm = max((len(i) for i in a))
a = padd(a, mm)
ans = [[] for i in range(n)]
ans[0] = [int(i) for i in a[0]]
max1 = 0
qq = []
for _ in range(m):
	(l, r) = map(int, input().split())
	max1 = max(max1, r)
	qq.append((l, r))
for j in range(mm):
	for i in range(1, len(a)):
		if len(a[i]) > j:
			if a[i][j] == '1':
				ans[i].append(ans[i - 1][j] + 1)
			else:
				ans[i].append(ans[i - 1][j])
for q in qq:
	(l, r) = q
	an = ['1' for _ in range(31)]
	for i in range(mm):
		if l > 1:
			if ans[r - 1][i] - ans[l - 2][i] >= (r - l + 1) / 2:
				an[i] = '0'
		elif ans[r - 1][i] >= r / 2:
			an[i] = '0'
	print(int(''.join(an[::-1]), 2))


def binary(N):
	bits = []
	while N != 0:
		bits.append(N % 2)
		N = int(N / 2)
	return bits

def decimal(bits):
	val = 0
	for bit in bits:
		val = val * 2 + bit
	return val
(N, Q) = [int(x) for x in input().strip().split(' ')]
A = [binary(int(x)) for x in input().strip().split(' ')]
A = [[]] + A
max_length = -1
for val in A:
	max_length = max(max_length, len(val))
for val in A:
	req_length = max_length - len(val)
	for _ in range(req_length):
		val.append(0)
for i in range(1, len(A)):
	for j in range(max_length):
		A[i][j] += A[i - 1][j]
for _ in range(Q):
	(L, R) = [int(x) for x in input().strip().split(' ')]
	bottom = A[R]
	top = A[L - 1]
	ans = []
	for i in range(max_length):
		num_ones = bottom[i] - top[i]
		num_zeroes = R - L + 1 - num_ones
		if num_zeroes <= num_ones:
			ans.append(0)
		else:
			ans.append(1)
	first = [1 for _ in range(31 - len(ans))]
	ans = first + ans[::-1]
	print(decimal(ans))


(N, Q) = map(int, input().split())
A = list(map(int, input().split()))
abi = [list(map(int, format(A[i], '031b'))) for i in range(N)]
cd = [[0 for i in range(31)] for i in range(N + 1)]
for i in range(1, N + 1):
	for j in range(31):
		cd[i][j] = cd[i - 1][j] + abi[i - 1][j]
temp = [0 for i in range(31)]
for query in range(Q):
	(l, r) = map(int, input().split())
	X = ''
	for i in range(31):
		temp[i] = cd[r][i] - cd[l - 1][i]
	for i in range(31):
		if temp[i] < r - l + 1 - temp[i]:
			X += '1'
		else:
			X += '0'
	print(int(X, 2))


(a, b) = map(int, input().split())
c = list(map(int, input().split()))
d = []
x = bin(c[0])
x = (33 - len(x)) * '0' + x[2:]
k = []
for i in range(31):
	if x[i] == '0':
		k.append(0)
	else:
		k.append(1)
d.append(k)
for i in range(1, a):
	x = bin(c[i])
	x = (33 - len(x)) * '0' + x[2:]
	k = []
	for j in range(31):
		if x[j] == '0':
			k.append(d[i - 1][j])
		else:
			k.append(d[i - 1][j] + 1)
	d.append(k)
for i in range(b):
	(l, r) = map(int, input().split())
	m = r - l + 1
	z = ''
	if l == 1:
		for j in range(31):
			if m % 2 == 0:
				if d[r - 1][j] >= m // 2:
					z = z + '0'
				else:
					z = z + '1'
			elif d[r - 1][j] > m // 2:
				z = z + '0'
			else:
				z = z + '1'
	else:
		for j in range(31):
			if m % 2 == 0:
				if d[r - 1][j] - d[l - 2][j] >= m // 2:
					z = z + '0'
				else:
					z = z + '1'
			elif d[r - 1][j] - d[l - 2][j] > m // 2:
				z = z + '0'
			else:
				z = z + '1'
	print(int(z, 2))


import math

def func1():
	return [int(x) for x in input().split()]
(n, q) = func1()
ll = func1()
m = [[0 for _ in range(31)]]
c1 = [0 for _ in range(31)]
for i in range(n):
	bb = '{:031b}'.format(ll[i])
	c2 = [c1[x] + int(bb[x]) for x in range(31)]
	m.append(c2)
	c1 = c2

def func2():
	(l, r) = func1()
	md = math.ceil((r - l + 1) / 2)
	p = []
	pp = 0
	for i in range(31):
		if m[r][i] - m[l - 1][i] < md:
			p.append('1')
		else:
			p.append('0')
	return int(''.join(p), 2)
a = []
for _ in range(q):
	a.append(func2())
for aa in a:
	print(aa)


(n, q) = map(int, input().split())
arr = [int(x) for x in input().split()]
new_array = []
for i in range(n):
	new_array.append([])
	for j in range(31):
		if arr[i] & 1 << j:
			if i == 0:
				new_array[i].append(1)
			else:
				new_array[i].append(new_array[i - 1][j] + 1)
		elif i == 0:
			new_array[i].append(0)
		else:
			new_array[i].append(new_array[i - 1][j])
for i in range(q):
	(x, y) = map(int, input().split())
	new_sum = 1
	max1 = 0
	mid = (y - x + 1) / 2
	for j in range(31):
		if x == 1:
			if new_array[y - 1][j] < mid:
				max1 += new_sum
		elif new_array[y - 1][j] - new_array[x - 2][j] < mid:
			max1 += new_sum
		new_sum *= 2
	print(max1)


from sys import setrecursionlimit, exit
from math import ceil, floor, acos, pi
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from functools import reduce
from collections import Counter
import queue
setrecursionlimit(10 ** 7)
RI = lambda x=' ': list(map(int, input().split(x)))
RS = lambda x=' ': input().rstrip().split(x)
dX = [-1, 1, 0, 0, -1, 1, -1, 1]
dY = [0, 0, -1, 1, 1, -1, -1, 1]
mod = int(1000000000.0 + 7)
eps = 1e-06
MAX = 2 ** 32
(N, Q) = RI()
A = RI()
s = [0] * 31
x = [s.copy()]
for n in A:
	i = 0
	while n:
		if n % 2:
			s[i] += 1
		n //= 2
		i += 1
	x.append(s.copy())
for _ in range(Q):
	(L, R) = RI()
	v = [x[R][i] - x[L - 1][i] for i in range(31)]
	ans = 0
	for i in range(31):
		if v[i] < (R - L + 1) / 2:
			ans += 2 ** i
	print(ans)


(n, q) = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
arra = [[0] * 31 for i in range(n + 1)]
for num in range(n):
	tempStr = bin(a[num])[2:][::-1]
	for i in range(31):
		arra[num + 1][i] = arra[num][i]
	for i in range(len(tempStr)):
		arra[num + 1][i] += int(tempStr[i])
ansarr = [0] * q
for z in range(q):
	(l, r) = [int(x) for x in input().split()]
	ans = [0] * 31
	for i in range(31):
		if arra[r][i] - arra[l - 1][i] < (r - l + 1) / 2:
			ans[i] = 1
	ans = ans[::-1]
	ansarr[z] = int('0b' + ''.join([str(x) for x in ans]), 2)
print('\n'.join([str(x) for x in ansarr]))


import numpy as np
(n, q) = map(int, input().strip().split())
arr = np.array(list(map(int, input().split())))
con = lambda val: [int(val) for val in np.binary_repr(val, width=31)]
mp = np.array(list(map(con, arr)))
zero = np.zeros(31, dtype=int)
ans = np.array(mp)
for i in range(1, len(mp)):
	ans[i] += ans[i - 1]
while q:
	q = q - 1
	(l, r) = map(int, input().strip().split())
	no = r - l + 1
	l = l - 1
	r = r - 1
	if l == 0:
		final_ans = ans[r]
	else:
		final_ans = ans[r] - ans[l - 1]
	mid = (no + 1) // 2
	count = 0
	for (i, val) in enumerate(reversed(final_ans)):
		if val < mid:
			count += 2 ** i
	print(count)


(n, q) = map(int, input().split())
arr = list(map(int, input().split()))
pres = [[0] * 31 for _ in range(n + 1)]
for i in range(1, n + 1):
	j = bin(arr[i - 1])[2:]
	j = j[::-1]
	for k in range(len(j)):
		pres[i][k] = int(j[k])
for i in range(1, n + 1):
	for k in range(31):
		pres[i][k] += pres[i - 1][k]
for i in range(q):
	(l, r) = map(int, input().split())
	tr = 2 ** 31 - 1
	x = 1
	for k in range(31):
		diff = pres[r][k] - pres[l - 1][k]
		if diff > (r - l) // 2:
			tr ^= x
		x *= 2
	print(tr)


(n, q) = [int(__) for __ in input().strip().split()]
arr = [int(__) for __ in input().strip().split()]
le = len(bin(max(arr))) - 2
for i in range(len(arr)):
	arr[i] = bin(arr[i])[2:].zfill(le)
dic = {}
for i in range(le):
	x = arr[0][i]
	pre = [1 if arr[0][i] == '1' else 0]
	for j in range(1, n):
		if arr[j][i] == '1':
			pre.append(pre[j - 1] + 1)
		else:
			pre.append(pre[j - 1])
	dic[i] = pre
for _ in range(q):
	ans = ['0' for i in range(le)]
	(l, r) = [int(__) for __ in input().strip().split()]
	(l, r) = (l - 1, r - 1)
	for i in range(le):
		ones = 0
		if l == 0:
			ones = dic[i][r]
		else:
			ones = dic[i][r] - dic[i][l - 1]
		zros = r - l + 1 - ones
		if zros > ones:
			ans[i] = '1'
		else:
			ans[i] = '0'
	print(int('1' * (31 - le) + ''.join(ans), 2))


import math

def reverse(s):
	str = ''
	for i in s:
		str = i + str
	return str
(n, q) = map(int, input().split())
A = list(map(int, input().split()))
a1 = []
val = [0] * 31
temp = [0] * 31
a1.append(temp)
for va in A:
	q2 = '{0:b}'.format(va)
	q1 = reverse(q2)
	for i in range(len(q1)):
		if q1[i] == '1':
			val[i] += 1
	a1.append(val[:])
for i in range(q):
	(l, r) = map(int, input().split())
	res = ''
	for j in range(31):
		if a1[r][j] - a1[l - 1][j] > math.floor((r - l) / 2):
			res += '0'
		else:
			res += '1'
	print(int(reverse(res), 2))


(n, q) = map(int, input().split())
a = list(map(int, input().split()))
a1 = []
l1 = []
val = [0] * 31
a1.append(val[:])
for x in a:
	w = '{0:b}'.format(x)
	w = w[::-1]
	l1.append(len(w))
	for i in range(len(w)):
		if w[i] == '1':
			val[i] += 1
	a1.append(val[:])
for i in range(q):
	(l, r) = map(int, input().split())
	ans = ''
	for j in range(31):
		if a1[r][j] - a1[l - 1][j] > (r - l) // 2:
			ans += '0'
		else:
			ans += '1'
	print(int(ans[::-1], 2))


def main():
	(n, q) = map(int, input().split())
	binary = ['{:031b}'.format(int(i)) for i in input().split()]
	zero = [[0 for i in range(n)] for j in range(31)]
	one = [[0 for i in range(n)] for j in range(31)]
	for pos in range(31):
		ones = 0
		zeroes = 0
		item_index = 0
		for item in binary:
			if item[pos] == '0':
				zeroes += 1
			elif item[pos] == '1':
				ones += 1
			zero[pos][item_index] = zeroes
			one[pos][item_index] = ones
			item_index += 1
	for queries in range(q):
		(l, r) = map(int, input().split())
		ans = ''
		for pos in range(31):
			if l == 1:
				ones = one[pos][r - 1]
				zeroes = zero[pos][r - 1]
			else:
				ones = one[pos][r - 1] - one[pos][l - 2]
				zeroes = zero[pos][r - 1] - zero[pos][l - 2]
			if ones < zeroes:
				ans = ans + '1'
			elif ones >= zeroes:
				ans = ans + '0'
		print(int(ans, 2))
main()


(N, Q) = [int(i) for i in input().split(' ')]
List = [int(i) for i in input().split(' ')]
List1 = [[0 for i in range(31)]]
Final_List1 = []
temp = 0
for i in List:
	Final_List = list(map(int, list(str('{0:031b}'.format(i)))))
	Final_List1 = []
	for j in range(31):
		Final_List1.append(Final_List[j] + List1[temp][j])
	List1.append(Final_List1)
	temp += 1
for _ in range(Q):
	(L, R) = [int(i) for i in input().split(' ')]
	num = (R - L + 1) / 2
	Final_List2 = []
	for j in range(31):
		if num <= List1[R][j] - List1[L - 1][j]:
			Final_List2.append('0')
		else:
			Final_List2.append('1')
	print(int(''.join(Final_List2), 2))


import sys
x = 2
x = [int(x) for x in sys.stdin.readline().split()]
n = x[0]
q = x[1]
l = [int(n) for n in sys.stdin.readline().split()]
b = []
M = 0
for i in range(n):
	t = []
	drain = [int(x) for x in list(bin(l[i])[2:])]
	for i in range(32 - len(drain)):
		t.append(0)
	t += drain[:]
	if M < len(drain):
		M = len(t)
	b.append(t)
for i in range(1, n):
	b[i] = [fi + se for (fi, se) in zip(b[i], b[i - 1])]
for _ in range(q):
	r = [int(x) for x in sys.stdin.readline().split()]
	d = r[1] - r[0]
	s = [0] * M
	svC = d // 2
	for i in range(M):
		if r[0] == 1:
			if b[r[1] - 1][i] <= svC:
				s[i] = 0
			else:
				s[i] = 1
		elif b[r[1] - 1][i] - b[r[0] - 2][i] <= svC:
			s[i] = 0
		else:
			s[i] = 1
	ans = 0
	for i in range(M):
		ans += 2 ** i * s[M - i - 1]
	print(2147483647 - ans)


import sys

def makeMatch(l):
	l.sort()
	(res, cnt) = ([], 1)
	for i in range(1, len(l)):
		if l[i] == l[i - 1]:
			cnt += 1
		else:
			res.append((l[i - 1], cnt))
			cnt = 1
		if i == len(l) - 1:
			res.append((l[i], cnt))
	return sorted(res, key=lambda x: (x[1], x[0]))
(n, q) = [int(x) for x in sys.stdin.readline().split()]
l = [int(n) for n in sys.stdin.readline().split()]
b = []
m = 0
for i in range(n):
	(t, tle) = ([], [int(x) for x in list(bin(l[i])[2:])])
	for i in range(32 - len(tle)):
		t.append(0)
	t += tle[:]
	if m < len(tle):
		m = len(t)
	b.append(t)
for i in range(1, n):
	b[i] = [fi + se for (fi, se) in zip(b[i], b[i - 1])]
for _ in range(q):
	r = [int(x) for x in sys.stdin.readline().split()]
	d = r[1] - r[0]
	s = [None] * m
	chk = d // 2
	for i in range(m):
		if r[0] == 1:
			if b[r[1] - 1][i] <= chk:
				s[i] = 0
			else:
				s[i] = 1
		elif b[r[1] - 1][i] - b[r[0] - 2][i] <= chk:
			s[i] = 0
		else:
			s[i] = 1
	ans = 0
	for i in range(m):
		ans += 2 ** i * s[m - i - 1]
	print(2147483647 - ans)


(N, Q) = [int(i) for i in input().split(' ')]
lis = [int(i) for i in input().split(' ')]
end_lis = [[0 for i in range(31)]]
l1 = []
temp = 0
for i in lis:
	l = list(map(int, list(str('{0:031b}'.format(i)))))
	l1 = []
	for j in range(31):
		l1.append(l[j] + end_lis[temp][j])
	end_lis.append(l1)
	temp += 1
for _ in range(Q):
	(L, R) = [int(i) for i in input().split(' ')]
	num = (R - L + 1) / 2
	final = []
	for j in range(31):
		if num <= end_lis[R][j] - end_lis[L - 1][j]:
			final.append('0')
		else:
			final.append('1')
	print(int(''.join(final), 2))


def prefix_sums(A):
	res = []
	for bit in range(31):
		res_bit = []
		cumsum = 0
		for a in A:
			cumsum += (a & 1 << bit) >> bit
			res_bit.append(cumsum)
		res.append(res_bit)
	return res

def main():
	(N, Q) = (int(_) for _ in input().split())
	A = [0] + [int(x) for x in input().split()]
	psums = prefix_sums(A)
	for _ in range(Q):
		(L, R) = (int(x) for x in input().split())
		length = R - L + 1
		res = 0
		for (psum, bit) in zip(psums, range(31)):
			ones = psum[R] - psum[L - 1]
			if 2 * ones < length:
				res = res + (1 << bit)
		print(res)
main()