Xorq has invented an encryption algorithm which uses bitwise XOR operations extensively. This encryption algorithm uses a sequence of non-negative integers $x=[x[1],x[2]\cdots x[n]]$ as its key. To implement this algorithm efficiently, Xorq needs to find maximum value of $(a\oplus x_j)$ for given integers $\class{ML__boldsymbol}{\boldsymbol{a}}$, $\boldsymbol{l}$ and $\textbf{r}$, such that, $l\leq j\leq r$. Help Xorq implement this function.  

For example, $x=[3,5,9]$, $\boldsymbol{a}=4$, $l=1$ and $r=3$.  We test each $x[j]$ for all values of $j$ between $\boldsymbol{l}$ and $\textbf{r}$ inclusive:

j   x[j]    x[j]^4
1   3       7
2   5       1
3   9       13

Our maximum value is $13$.

Function Description

Complete the xorKey function in the editor below.  It should return an integer array where each value is the response to a query.

xorKey has the following parameters:  

x: a list of integers  
queries: a two dimensional array where each element is an integer array that consists of $a[i],l[i],r[i]$ for the $i^{\mbox{th}}$ query at indices $\mathbf{0,1}$ and $2$ respectively.  

Input Format

The first line contains an integer $\boldsymbol{\boldsymbol{t}}$, the number of test cases. 

The first line of each test case contains two space-separated integers $n$ and $\textit{q}$, the size of the integer array $\boldsymbol{x}$ and the number of queries against the test case. 

The next line contains $n$ space-separated integers $x[j]$. 

Each of next $\textit{q}$ lines describes a query which consists of three integers $a[i],\ l[i]$ and $r[i]$.   

Constraints

$1\leq n\leq100000$ 

$1\leq q\leq50000$ 

$0\leq x[j],a[i]\leq2^{15}$ 

$1\leq l[i],r[i]\leq n$  

Output Format

For each query, print the maximum value for $\left(a[i]\oplus x[j]\right)$, such that, $l[i]\leq j\leq r[i]$ on a new line.  

Sample Input 0
1
15 8
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
10 6 10
1023 7 7
33 5 8
182 5 10
181 1 13
5 10 15
99 8 9
33 10 14

Sample Output 0
13
1016
41
191
191
15
107
47

Explanation 0

First Query (10 6 10): $x_6\oplus10=12,x_7\oplus10=13,x_8\oplus10=2,x_9\oplus10=3,x_{10}\oplus10=0$.  The maximum is $13$.  

Second Query (1023 7 7): $x_7\oplus1023=1016$  

Third Query (33 5 8): $x_5\oplus33=36,x_6\oplus33=39,x_7\oplus33=38,x_8\oplus33=41$   

Fourth Query (182 5 10): $\textbf{x}_5\oplus182=179,\textbf{x}_6\oplus182=176,\textbf{x}_7\oplus182=177,\textbf{x}_8\oplus182=190,\textbf{x}_9\oplus182=191,\textbf{x}_{20}\oplus182=188$

Source: hackerrank | Difficulty: HARD
Tags: Bit manipulation


Solutions:
from sys import stderr
MAXBITS = 15

def main():
	ncases = int(input())
	for case in range(ncases):
		(arrsize, nqueries) = readints()
		arr = readints()
		assert arrsize == len(arr)
		finder = XORkeyfinder(arr)
		for query in range(nqueries):
			(a, start, stop) = readints()
			print(finder.findmax(a, start - 1, stop))

def readints():
	return [int(f) for f in input().split()]

class XORkeyfinder:

	def __init__(self, arr):
		self.tbl = []
		self.arr = arr
		for i in range(MAXBITS):
			shift = MAXBITS - i - 1
			prev = [None] * (2 << i)
			row = [len(arr)] * len(arr)
			chain = [None] * len(arr)
			for (loc, x) in enumerate(arr):
				x = x >> shift
				p = prev[x ^ 1]
				while p is not None:
					row[p] = loc
					p = chain[p]
				prev[x ^ 1] = None
				chain[loc] = prev[x]
				prev[x] = loc
			self.tbl.append(row)

	def findmax(self, a, start, stop, MAXBITS=MAXBITS):
		(arr, tbl) = (self.arr, self.tbl)
		comp = ~a
		(best, bestloc) = (arr[start], start)
		for (i, row) in enumerate(tbl):
			test = 1 << MAXBITS - i - 1
			if comp & test != best & test:
				newloc = row[bestloc]
				if newloc < stop:
					(best, bestloc) = (arr[newloc], newloc)
		return best ^ a
main()


import random
from bisect import bisect, bisect_left
LIMT = 15

def as_list(f):

	def _f(*args, **kwargs):
		return list(f(*args, **kwargs))
	return _f

def preprocess(xs):
	return list(xs)

def solve_brute_force(ys, a, p, q):
	return max((a ^ y for y in ys[p - 1:q]))

def to_bits(x):
	return map(int, bin(x)[2:].zfill(LIMT))

def inline(trie, bs, index):
	for b in bs:
		trie[2].append(index)
		if trie[b] is None:
			trie[b] = [None, None, []]
		trie = trie[b]
	trie[2].append(index)

def preprocess(xs):
	trie = [None, None, []]
	for (i, bs) in enumerate(map(to_bits, xs)):
		inline(trie, bs, i)
	return trie

def complement(bs):
	return [0 if b else 1 for b in bs]

def overlaps(xs, p, q):
	if not xs:
		return False
	(x_lo, x_hi) = (xs[0], xs[-1])
	if p <= x_lo:
		return x_lo <= q
	elif p <= x_hi <= q:
		return True
	(hi, lo) = (len(xs) - 1, 0)
	while hi - lo > 1:
		mid = (hi + lo) // 2
		mx = xs[mid]
		if p <= mx <= q:
			return True
		elif mx < p:
			lo = mid
		else:
			hi = mid
	return any((p <= x <= q for x in xs[lo:hi + 1]))

def find_max_xor_index(trie, x, p, q):
	for b in complement(to_bits(x)):
		if trie[b] is not None:
			if trie[not b] is None or overlaps(trie[b][2], p, q):
				trie = trie[b]
			else:
				trie = trie[not b]
		else:
			trie = trie[not b]
	return trie[2][0]

def random_bits(n=10000):
	return to_bits(random.randint(0, n))

def random_trie(n=10000, k=100):
	return preprocess((random.randint(0, k) for _ in range(k)))

def test_run(n=10000, k=100, cases=1000):
	r_trie = random_trie(n=n, k=k)
	for _ in range(cases):
		find_max_xor_index(r_trie, random.randint(0, n), 0, k)

def test(in_file, out_file):
	with open(in_file) as f:
		ins = iter(f.readlines())
	with open(out_file) as f:
		outs = iter(f.readlines())
	T = int(next(ins))
	for _ in range(T):
		(N, Q) = map(int, next(ins).split())
		xs = list(map(int, next(ins).split()))
		print('Starting preprocess with N={} Q={}'.format(N, Q))
		trie = preprocess(xs)
		print('Done with preprocess')
		for i in range(Q):
			if i % 1000 == 0:
				print(N, Q, i)
			(a, p, q) = map(int, next(ins).split())
			max_xor_index = find_max_xor_index(trie, a, p - 1, q - 1)
			sol = xs[max_xor_index] ^ a

def main():
	T = int(input())
	for _ in range(T):
		(N, Q) = map(int, input().split())
		xs = list(map(int, input().split()))
		trie = preprocess(xs)
		for _ in range(Q):
			(a, p, q) = map(int, input().split())
			max_xor_index = find_max_xor_index(trie, a, p - 1, q - 1)
			print(a ^ xs[max_xor_index])
main()


import bisect

def trie_insert(t, n, i):
	for j in range(14, 0, -1):
		b = n >> j & 1
		if t[b] == None:
			t[b] = [None, None]
		t = t[b]
	b = n & 1
	if t[b] == None:
		t[b] = [i]
	else:
		t[b].append(i)

def to_int(f):
	m = 0
	for i in range(15):
		m += f[i] << i
	return m

def trie_search(t, a, p, q):
	s = [None] * 15
	f = [2] * 15
	j = 14
	while j < 15:
		if f[j] == 2:
			b = a >> j & 1
			s[j] = t[b]
			t = t[b ^ 1]
			f[j] = 1
		elif f[j] == 1:
			t = s[j]
			f[j] = 0
		else:
			j += 1
			continue
		if t:
			if j:
				j -= 1
				f[j] = 2
			else:
				i = bisect.bisect_left(t, p)
				if i < len(t) and t[i] <= q:
					return to_int(f)
	return -1
T = int(input())
for t in range(T):
	(N, Q) = map(int, input().split())
	nums = [int(x) for x in input().split()]
	trie = [None, None]
	for i in range(N):
		trie_insert(trie, nums[i], i + 1)
	for i in range(Q):
		(a, p, q) = map(int, input().split())
		print(trie_search(trie, a, p, q))


def normalized_bin(x):
	x = [int(t) for t in bin(x)[2:]]
	return [0] * (15 - len(x)) + x

def add_list(data, L, f, t, p):
	if L[f][1] & p:
		data[1] = {'w': data['w'] if 'w' in data else sorted((i for (i, v) in L[f:t]))}
		if p > 1:
			add_list(data[1], L, f, t, p >> 1)
		return
	if not L[t - 1][1] & p:
		data[0] = {'w': data['w'] if 'w' in data else sorted((i for (i, v) in L[f:t]))}
		if p > 1:
			add_list(data[0], L, f, t, p >> 1)
		return
	l = f
	r = t - 1
	while l < r:
		mi = l + r >> 1
		m = L[mi][1]
		if not m & p:
			l = mi + 1
		else:
			r = mi - 1
	if L[l][1] & p:
		m = l if l <= f or not L[l - 1][1] & p else l - 1
	else:
		m = l + 1
	data[0] = {'w': sorted((i for (i, v) in L[f:m]))}
	data[1] = {'w': sorted((i for (i, v) in L[m:t]))}
	p >>= 1
	if p:
		add_list(data[0], L, f, m, p)
		add_list(data[1], L, m, t, p)
t = int(input())
for _ in range(t):
	(n, q) = [int(tmp) for tmp in input().strip().split()]
	x_list = [int(t) for t in input().strip().split()]
	L = list(enumerate(x_list, start=1))
	L.sort(key=lambda t: t[1])
	data = dict()
	add_list(data, L, 0, len(L), 1 << 14)
	for _ in range(q):
		(a, p, q) = [int(tmp) for tmp in input().strip().split()]
		tmp = data
		for d in normalized_bin(a):
			if 1 - d in tmp:
				if d not in tmp:
					tmp = tmp[1 - d]
				else:
					idxes = tmp[1 - d]['w']
					l = 0
					r = len(idxes) - 1
					while l <= r:
						mi = l + r >> 1
						m = idxes[mi]
						if p > m:
							l = mi + 1
						elif q < m:
							r = mi - 1
						else:
							tmp = tmp[1 - d]
							break
					else:
						tmp = tmp[d]
			else:
				tmp = tmp[d]
		print(a ^ x_list[tmp['w'][0] - 1])


from functools import reduce
import bisect
NBITS = 15
ALLONES = (1 << NBITS) - 1

def lookup(low, high, data):
	left = bisect.bisect_left(data, low)
	right = bisect.bisect_right(data, high)
	n = right - left
	return None if n <= 0 else -data[left] - 1 if n > 1 else data[left]

def getMatch(goal, low, high, index, bit):
	ind = index[bit]
	data = ind[goal >> bit]
	return lookup(low, high, data) if data else None

def matchImpossible(andOfX, orOfX, goal, mask):
	gm = goal & mask
	return gm == 0 and andOfX & mask == mask or (gm == mask and orOfX & mask == 0)

def solve(andOfX, orOfX, goal, low, high, index):
	bit = 8
	mask = (1 << bit) - 1
	highMask = ALLONES & ~mask
	if matchImpossible(andOfX, orOfX, goal, highMask):
		goal = ALLONES & ~goal & highMask | goal & mask
		bit -= 1
		match = None
	else:
		bit = 7
		match = getMatch(goal, low, high, index, bit)
		if match == None:
			bit = 11
			match = getMatch(goal, low, high, index, bit)
			if match == None:
				bit = NBITS - 1
		else:
			bit2 = 3
			match2 = getMatch(goal, low, high, index, bit2)
			if match2 != None:
				(bit, match) = (bit2, match2)
	if match == None:
		while bit >= 0:
			match = getMatch(goal, low, high, index, bit)
			if match != None:
				break
			goal ^= 1 << bit
			bit -= 1
	bit -= 1
	while bit >= 0 and match < 0:
		match = getMatch(goal, low, high, index, bit)
		if match == None:
			goal ^= 1 << bit
			match = getMatch(goal, low, high, index, bit)
		bit -= 1
	return match if match >= 0 else -match - 1

def buildIndexFor(x, bit):
	size = 1 << NBITS - bit
	vec = [[] for _ in range(size)]
	for (i, v) in enumerate(x):
		vec[v >> bit].append(i)
	return vec

def buildIndex(x):
	index = [buildIndexFor(x, b) for b in range(NBITS)]
	return index

def findHighBit(x):
	r = 0
	x >>= 1
	while x:
		r += 1
		x >>= 1
	return r

def andFun(x, y):
	return x & y

def orFun(x, y):
	return x | y

def main():
	t = int(input())
	for _t in range(t):
		(_n, nq) = [int(i) for i in input().split()]
		x = [int(i) for i in input().split()]
		index = buildIndex(x)
		andOfX = reduce(andFun, x, ALLONES)
		orOfX = reduce(orFun, x, 0)
		for _q in range(nq):
			(a, low, high) = [int(i) for i in input().split()]
			goal = ALLONES ^ a
			ibest = solve(andOfX, orOfX, goal, low - 1, high - 1, index)
			answer = a ^ x[ibest]
			print(answer)
main()


def build_trie(sequence):
	root = [None, None, [], []]
	for (idx, item) in enumerate(sequence):
		current = root
		for shift in range(14, -1, -1):
			bit = item >> shift & 1
			if current[bit] is None:
				current[bit] = [None, None, [], []]
			current[bit + 2].append(idx)
			current = current[bit]
	return root

def range_in_ordered_list(ordlist, minrange, maxrange):
	min_index = 0
	max_index = len(ordlist)
	while True:
		index = min_index + (max_index - min_index >> 1)
		value = ordlist[index]
		if value >= minrange and value <= maxrange:
			return True
		if max_index <= min_index + 1:
			return False
		if value >= maxrange:
			max_index = index
		elif value < minrange:
			min_index = index

def get_max_xor_in_trie(nums, root, a, minrange, maxrange):
	besta = 32767 & ~a
	for shift in range(14, 0, -1):
		bit = besta >> shift & 1
		if root[bit] == None or not range_in_ordered_list(root[bit + 2], minrange, maxrange):
			bit = bit ^ 1
		root = root[bit]
	bit = besta & 1
	if root[bit] == None or not range_in_ordered_list(root[bit + 2], minrange, maxrange):
		bit = bit ^ 1
	return nums[root[bit + 2][0]] ^ a
t = int(input().strip())
for ti in range(t):
	(n, q) = [int(x) for x in input().strip().split()]
	numbers = [int(x) for x in input().strip().split()]
	root = build_trie(numbers)
	for i in range(q):
		(ai, pi, qi) = [int(x) for x in input().strip().split()]
		res0 = get_max_xor_in_trie(numbers, root, ai, pi - 1, qi - 1)
		print(res0)


for _ in range(int(input())):
	(N, Q) = map(int, input().split())
	x = list(map(int, input().split()))
	assert len(x) == N
	queries = []
	for j in range(Q):
		(a, p, q) = map(int, input().split())
		assert 1 <= p <= q <= N
		queries.append((q - 1, p - 1, a, j))
	assert len(queries) == Q
	queries.sort()
	answers = [0] * Q
	maxi = [-1] * 65536
	qnxt = 0
	for i in range(N):
		xi = x[i]
		assert 0 <= xi < 32768
		k = xi + 32768
		while k > 0:
			if maxi[k] < i:
				maxi[k] = i
			k //= 2
		while qnxt < Q and queries[qnxt][0] == i:
			(q, p, a, j) = queries[qnxt]
			qnxt += 1
			k = 1
			b = 14
			while b >= 0:
				prefer = 1 - (a >> b) & 1
				k = 2 * k + prefer
				if maxi[k] < p:
					k ^= 1
				assert maxi[k] >= p
				b -= 1
			assert k >= 32768
			answers[j] = a ^ k - 32768
	for v in answers:
		print(v)


from bisect import bisect
(MK, MK1, MF, rs) = (32768, 32767, [32767 ^ 1 << i for i in range(15)], '')
(IPOS, ILEN, INEXT) = ([None] * MK, [0] * MK, [None] * MK)
for _ in range(int(input())):
	(N, Q) = map(int, input().split(' '))
	DATA = [int(x) for x in input().split(' ')]
	for i in range(MK):
		ILEN[i] = 0
	for x in DATA:
		ILEN[x] += 1
	for i in range(MK):
		IPOS[i] = [0] * ILEN[i]
		ILEN[i] = 0
	for i in range(N):
		x = DATA[i]
		IPOS[x][ILEN[x]] = i
		ILEN[x] += 1
	NEL = list(filter(lambda x: ILEN[x], range(MK)))
	for _ in range(Q):
		(a, p, q) = map(int, input().split(' '))
		(p, q) = (p - 1, q - 1)
		for PMK in sorted(map(lambda v: v ^ a, NEL))[::-1] if len(NEL) < 1000 else range(MK1, -1, -1):
			fa = PMK ^ a
			if ILEN[fa] == 0:
				continue
			fap = IPOS[fa]
			if not (fap[0] > q or fap[-1] < p) and fap[bisect(fap, p - 1)] <= q:
				rs += str(PMK)
				rs += '\n'
				break
print(rs)


from sys import stderr
MAXBITS = 15

def main():
	ncases = int(input())
	for case in range(ncases):
		(arrsize, nqueries) = readints()
		arr = readints()
		assert arrsize == len(arr)
		finder = XORkeyfinder(arr)
		for query in range(nqueries):
			(a, start, stop) = readints()
			print(finder.findmax(a, start - 1, stop))

def readints():
	return [int(f) for f in input().split()]

class XORkeyfinder:

	def __init__(self, arr):
		self.tbl = []
		self.arr = arr
		for i in range(MAXBITS):
			shift = MAXBITS - i - 1
			prev = [None] * (2 << i)
			row = [len(arr)] * len(arr)
			chain = [None] * len(arr)
			for (loc, x) in enumerate(arr):
				x = x >> shift
				p = prev[x ^ 1]
				while p is not None:
					row[p] = loc
					p = chain[p]
				prev[x ^ 1] = None
				chain[loc] = prev[x]
				prev[x] = loc
			self.tbl.append(row)

	def findmax(self, a, start, stop, MAXBITS=MAXBITS):
		(arr, tbl) = (self.arr, self.tbl)
		comp = ~a
		(best, bestloc) = (arr[start], start)
		for (i, row) in enumerate(tbl):
			test = 1 << MAXBITS - i - 1
			if comp & test != best & test:
				newloc = row[bestloc]
				if newloc < stop:
					(best, bestloc) = (arr[newloc], newloc)
		return best ^ a
main()