Devendra loves the XOR operation very much which is denoted by $\land\operatorname$ sign in most of the programming languages. He has a list $\mbox{A}$ of $N$ numbers and he wants to know the answers of $\mbox{M}$ queries. Each query will be denoted by three numbers i.e. $K,P,R$ .

For query $K,P\ \text{and}\ R$, he has to print the value of the $\textit{KPRsum}$ which can be described as given below. As the value of the $\textit{KPRsum}$ can be large. So, print it modulus $(10^9+7)$.

$KPRsum=\sum_{i=P}^{R-1}\sum_{j=i+1}^R\left(K\oplus\left(A[i]\oplus A[j]\right)\right)$

Input Format 

The first line contains an integer $N$, i.e., the number of the elements in the list. List is numbered from $\mbox{1}$ to $N$. 

Next line will contain $N$ space seperated integers. 

Third line will contain a number $\mbox{M}$ i.e. number of queries followed by $\mbox{M}$ lines each containing  integers $K,P\&R$.

Output Format 

Print $\mbox{M}$ lines, $i^{\mbox{th}}$ line will be answer of $i^{\mbox{th}}$ query. Answer will be 0 in case of P=R.

Constraints 

$1\leq N\leq10^5$ 

$1\leq A[i]\leq10^6$ 

$1\leq M\leq10^5$ 

$0\leq K\leq10^6$ 

$1\leq P\leq R\leq N$

Sample Input  

3
1 2 3
2
1 1 3
2 1 3

Sample Output  

5
4

Explanation

For first query, it will will be $(1\oplus(1\oplus2))+(1\oplus(1\oplus3))+(1\oplus(2\oplus3))=5$

Difficulty: MEDIUM_HARD
Tags: Matrices

Starter code:

Solutions:
MOD = 10 ** 9 + 7
MAXBITS = 20

def main():
	n = int(input())
	arr = readints()
	assert n == len(arr)
	arrsum1 = sum1(arr)
	n = int(input())
	for _ in range(n):
		(k, p, r) = readints()
		print(solve(arrsum1, k, p, r))

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

def sum1(arr):
	ans = [[0] * MAXBITS]
	for a in arr:
		bits = bitarr(a)
		ans.append([x + y for (x, y) in zip(bits, ans[-1])])
	return ans

def bitarr(a):
	return [a >> i & 1 for i in range(MAXBITS)]

def solve(sum1, k, p, r):
	k = bitarr(k)
	npairs = (r - p + 1) * (r - p) // 2
	count1 = [rc - pc for (rc, pc) in zip(sum1[r], sum1[p - 1])]
	ans = 0
	for (i, (inv, c1)) in enumerate(zip(k, count1)):
		ones = c1 * (r - p + 1 - c1)
		if inv == 1:
			ones = npairs - ones
		ans += ones << i
	return ans % MOD
main()


from random import randint
from collections import Counter
from itertools import accumulate
home = 0
lire = 0
trace = 0
if home:
	from mesures import ch
modo = 10 ** 9 + 7

def toiLb(N):
	return list((int(j) for j in list(reversed(bin(N)))[:-2]))

def toiLb(N, lgmin):
	return list((int(j) for j in list(reversed(bin(N)))[:-2])) + [0] * (lgmin - N.bit_length())

def fromiLb(iN):
	(b, r) = (1, 0)
	for ix in range(len(iN)):
		r += b * iN[ix]
		b <<= 1
	return r

def chk(li, K):
	return sum((sum((K ^ li[i] ^ li[j] for j in range(i + 1, len(li)))) % modo for i in range(len(li) - 1))) % modo

def bbadd(A, B):
	lg = min(len(A), len(B))
	if len(A) < len(B):
		(A, B) = (B, A)
	for ib in range(lg):
		A[ib] += B[ib]
	return A

def evalBits(ui, zi):
	return (ui * zi, ui * (ui - 1) // 2 + zi * (zi - 1) // 2)

def parBits(li, k):
	if trace:
		print(li)
	pb = Counter()
	lgl = len(li)
	if not lgl:
		return 0
	for l in li:
		for ib in range(l.bit_length()):
			if l & 1:
				pb[ib] += 1
			l >>= 1
	res = 0
	mk = max(pb.keys())
	for ib in range(max(k.bit_length(), mk + 1)):
		(ui, zi) = (pb[ib], lgl - pb[ib])
		(uo, zo) = evalBits(ui, zi)
		if k & 1:
			res += (1 << ib) * zo
		else:
			res += (1 << ib) * uo
		res %= modo
		k >>= 1
	return res

def enLongueur(li, lpr):
	nbbits = max(li).bit_length()
	mb = 1
	parBit = [None] * nbbits
	if trace & 1:
		print(parBit, nbbits)
	for ib in range(nbbits):
		parPos = list(accumulate((int(i & mb != 0) for i in li)))
		parBit[ib] = dict(((pr, parPos[pr]) for pr in [0] + lpr))
		mb <<= 1
	return parBit

def query(q, parBit):
	(res, mk) = (0, 1)
	(K, P, R) = q
	for ib in range(max(K.bit_length(), len(parBit))):
		ui = parBit[ib][R] - parBit[ib][P - 1]
		zi = R - P + 1 - ui
		(uo, zo) = evalBits(ui, zi)
		res += (1 << ib) * (zo if K & 1 else uo)
		res %= modo
		K >>= 1
	return res
if home and (not lire):
	(nbnb, nbq) = (50, 20)
	s = [0] + list((randint(0, 10 ** 6) for i in range(nbnb)))
	ql = [[23, 1, 5]]
	for _ in range(nbq):
		P = randint(1, nbnb - 1)
		R = randint(P, nbnb)
		ql += [[randint(0, 10 ** 6), P, R]]
	if nbnb < 11:
		print(s)
	if nbq < 11:
		print(ql)
else:
	s = []
	input()
	s = [0] + list(map(int, input().strip().split()))
	if home and len(s) < 10:
		print(s)
	ql = []
	for _ in range(int(input().strip())):
		ql += [list(map(int, input().strip().split()))]
	if home and len(ql) < 10:
		for q in ql:
			print(q)
spr = set(list((i[1] - 1 for i in ql)) + list((i[2] for i in ql)))
lpr = sorted(spr)
parBit = enLongueur(s, lpr)
if home:
	if len(lpr) < 11:
		print(lpr)
	if len(parBit[0]) < 100:
		for d in parBit:
			print(sorted(d.items()))
for q in ql:
	(K, P, R) = q
	if home and len(s) < 52 and (len(ql) < 22):
		(r, v) = (query(q, parBit), chk(s[P:R + 1], K))
		print(r == v, q, K, P, R, s[P:R + 1], r, v)
	else:
		print(query(q, parBit))


def kprsum_precompute(A, bit_masks):
	bit_counts = []
	bit_count_array = [0 for _ in range(0, 20)]
	for a in A:
		for j in range(0, len(bit_masks)):
			if a & bit_masks[j]:
				bit_count_array[j] += 1
		bit_counts.append(list(bit_count_array))
	return bit_counts

def kprsum_compute(A, bit_counts, bit_masks, K, P, R, mod):
	total_kprsum = 0
	for i in range(0, 20):
		if K & bit_masks[i]:
			if P == 0:
				total_kprsum += bit_masks[i] * (bit_counts[R][i] * (bit_counts[R][i] - 1) + (R - bit_counts[R][i] + 1) * (R - bit_counts[R][i])) // 2
			else:
				total_kprsum += bit_masks[i] * ((bit_counts[R][i] - bit_counts[P - 1][i]) * (bit_counts[R][i] - bit_counts[P - 1][i] - 1) + (R - P + 1 - bit_counts[R][i] + bit_counts[P - 1][i]) * (R - P - bit_counts[R][i] + bit_counts[P - 1][i])) // 2
		elif P == 0:
			total_kprsum += bit_masks[i] * (R - bit_counts[R][i] + 1) * bit_counts[R][i]
		else:
			total_kprsum += bit_masks[i] * (R - P + 1 - bit_counts[R][i] + bit_counts[P - 1][i]) * (bit_counts[R][i] - bit_counts[P - 1][i])
		total_kprsum %= mod
	return total_kprsum
modulus = pow(10, 9) + 7
N = int(input())
A = [int(a) for a in input().split()]
Q = int(input())
bit_masks = [pow(2, i) for i in range(0, 20)]
bit_counts = kprsum_precompute(A, bit_masks)
for _ in range(Q):
	(K, P, R) = [int(x) for x in input().split()]
	print(kprsum_compute(A, bit_counts, bit_masks, K, P - 1, R - 1, modulus))


mod = 10 ** 9 + 7
N = int(input())
A = [int(x) for x in input().split()]
M = int(input())
C = []
for i in range(20):
	R = [0]
	t = 0
	for x in A:
		t += x >> i & 1
		R.append(t)
	C.append(R)
for m in range(M):
	(K, P, R) = map(int, input().split())
	d = R - P + 1
	t = 0
	for i in range(20):
		n1 = C[i][R] - C[i][P - 1]
		n0 = d - n1
		if K >> i & 1:
			x = n1 * (n1 - 1) + n0 * (n0 - 1) >> 1
		else:
			x = n1 * n0
		t = (t + (x << i)) % mod
	print(t)


mod = 10 ** 9 + 7
N = int(input())
A = [int(x) for x in input().split()]
M = int(input())
C = []
for i in range(20):
	R = [0]
	t = 0
	for x in A:
		t += x >> i & 1
		R.append(t)
	C.append(R)
for m in range(M):
	(K, P, R) = map(int, input().split())
	d = R - P + 1
	t = 0
	for i in range(20):
		n1 = C[i][R] - C[i][P - 1]
		n0 = d - n1
		if K >> i & 1:
			x = n1 * (n1 - 1) + n0 * (n0 - 1) >> 1
		else:
			x = n1 * n0
		t = (t + (x << i)) % mod
	print(t)


import os
import sys
N = 20
N2 = 2 * N
mod = 1000000007

def prepare(n, A):
	nA = [0 for j in range(N2 * (n + 1))]
	for i in range(n):
		v = A[i]
		offset = (i + 1) * N2
		for j in range(0, N2, 2):
			nA[offset + j + v % 2] += 1
			v >>= 1
	for i in range(1, n + 1):
		offset = i * N2
		offset2 = offset - N2
		for j in range(0, N2, 2):
			nA[offset + j] += nA[offset2 + j]
			nA[offset + j + 1] += nA[offset2 + j + 1]
	return nA

def solve(nA, k, p, r):
	diff = [0 for i in range(2 * N)]
	r = r * N2
	p = (p - 1) * N2
	for i in range(0, N2, 2):
		diff[i] = nA[r + i] - nA[p + i]
		diff[i + 1] = nA[r + i + 1] - nA[p + i + 1]
	for i in range(0, N2, 2):
		z = diff[i]
		o = diff[i + 1]
		(diff[i], diff[i + 1]) = (o * (o - 1) + z * (z - 1) >> 1, z * o)
	ret = 0
	for i in range(0, N2, 2):
		t = diff[i] if k % 2 else diff[i + 1]
		t = t << i // 2
		if t >= mod:
			t %= mod
		ret += t
		if ret >= mod:
			ret %= mod
		k >>= 1
	return ret
n = int(input())
A = list(map(int, input().rstrip().split()))
nA = prepare(n, A)
m = int(input())
for i in range(m):
	(k, p, r) = list(map(int, input().rstrip().split()))
	print(solve(nA, k, p, r))


MOD = 10 ** 9 + 7

def mod(x):
	return x % MOD

def prepare(A):
	limit = 20
	mask = [1] * limit
	for i in range(limit):
		mask[i] = mask[i] << i
	cs = tuple(([] for _ in range(limit)))
	(a, m) = (A[0], mask[0])
	for (m, c) in zip(mask, cs):
		c.append((m & a) // m)
	for a in A[1:]:
		for (m, c) in zip(mask, cs):
			c.append((m & a) // m + c[-1])
	return (mask, cs)

def solve(K, P, R, env):
	if P == R:
		return 0
	(P, R, L) = (P - 1, R - 1, R - P)
	D = L * (L + 1) // 2
	S = 0
	for (m, c) in zip(*env):
		k = (K & m) // m
		n1 = c[R] - (c[P - 1] if P > 0 else 0)
		n1 = n1 * (L + 1 - n1)
		if k == 0:
			S = mod(S + n1 * m)
		else:
			S = mod(S + (D - n1) * m)
	return S
_ = input()
A = input().strip()
A = tuple((int(x) for x in A.split()))
E = prepare(A)
nt = int(input())
for _ in range(nt):
	line = input().strip().split(' ')
	(K, P, R) = map(int, line)
	print(solve(K, P, R, E))


n = int(input())
a = list(map(int, input().split(' ')))
adiglist = [[0] * 20]
for i in range(n):
	row = [0] * 20
	for j in range(20):
		row[j] = adiglist[-1][j] + (a[i] >> j) % 2
	adiglist.append(row)
mod = 1000000007
m = int(input())
for _ in range(m):
	[k, p, r] = list(map(int, input().split(' ')))
	tot = 0
	pow2 = 1
	for i in range(20):
		num1s = adiglist[r][i] - adiglist[p - 1][i]
		num0s = r - p + 1 - num1s
		num1pair = 2 * num1s * num0s
		num0pair = (r - p + 1) * (r - p + 1) - (r - p + 1) - num1pair
		tot += pow2 * (num1pair if (k >> i) % 2 == 0 else num0pair)
		pow2 = pow2 * 2
	print(tot // 2 % mod)


mod = 10 ** 9 + 7
N = int(input())
A = [int(x) for x in input().split()]
M = int(input())
C = []
for i in range(20):
	R = [0]
	t = 0
	for x in A:
		t += x >> i & 1
		R.append(t)
	C.append(R)
for m in range(M):
	(K, P, R) = map(int, input().split())
	d = R - P + 1
	t = 0
	for i in range(20):
		n1 = C[i][R] - C[i][P - 1]
		n0 = d - n1
		if K >> i & 1:
			x = n1 * (n1 - 1) + n0 * (n0 - 1) >> 1
		else:
			x = n1 * n0
		t = (t + (x << i)) % mod
	print(t)


def study(A):
	n = len(A)
	a = memoryview(bytearray(4 * 20 * n)).cast('I', (n, 20))
	for (i, ai) in enumerate(A):
		for j in range(20):
			a[i, j] = 1 & ai >> j
	for j in range(20):
		s = a[0, j]
		for i in range(1, n):
			s += a[i, j]
			a[i, j] = s
	return a

def solve(a, K, P, R):
	MOD = 10 ** 9 + 7
	total = R - P + 1
	plane = [0] * 20
	for j in range(20):
		count1 = a[R, j] - a[P - 1, j]
		count0 = total - count1
		plane[j] = count0 * count1
		if K >> j & 1:
			plane[j] = total * (total - 1) // 2 - plane[j]
	return sum((plane[j] * pow(2, j, MOD) % MOD for j in range(20))) % MOD
input()
A = [0]
A.extend(map(int, input().split()))
a = study(A)
for _ in range(int(input())):
	(K, P, R) = map(int, input().split())
	print(solve(a, K, P, R))


MOD = 10 ** 9 + 7
MAXBITS = 20

def main():
	n = int(input())
	arr = readints()
	assert n == len(arr)
	arrsum1 = sum1(arr)
	n = int(input())
	for _ in range(n):
		(k, p, r) = readints()
		print(solve(arrsum1, k, p, r))

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

def sum1(arr):
	ans = [[0] * MAXBITS]
	for a in arr:
		bits = bitarr(a)
		ans.append([x + y for (x, y) in zip(bits, ans[-1])])
	return ans

def bitarr(a):
	return [a >> i & 1 for i in range(MAXBITS)]

def solve(sum1, k, p, r):
	k = bitarr(k)
	npairs = (r - p + 1) * (r - p) // 2
	count1 = [rc - pc for (rc, pc) in zip(sum1[r], sum1[p - 1])]
	ans = 0
	for (i, (inv, c1)) in enumerate(zip(k, count1)):
		ones = c1 * (r - p + 1 - c1)
		if inv == 1:
			ones = npairs - ones
		ans += ones << i
	return ans % MOD
main()


MOD = 10 ** 9 + 7
MAXBITS = 20

def main():
	n = int(input())
	arr = readints()
	assert n == len(arr)
	arrsum1 = sum1(arr)
	n = int(input())
	for _ in range(n):
		(k, p, r) = readints()
		print(solve(arrsum1, k, p, r))

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

def sum1(arr):
	ans = [[0] * MAXBITS]
	for a in arr:
		bits = bitarr(a)
		ans.append([x + y for (x, y) in zip(bits, ans[-1])])
	return ans

def bitarr(a):
	return [a >> i & 1 for i in range(MAXBITS)]

def solve(sum1, k, p, r):
	k = bitarr(k)
	npairs = (r - p + 1) * (r - p) // 2
	count1 = [rc - pc for (rc, pc) in zip(sum1[r], sum1[p - 1])]
	ans = 0
	for (i, (inv, c1)) in enumerate(zip(k, count1)):
		ones = c1 * (r - p + 1 - c1)
		if inv == 1:
			ones = npairs - ones
		ans += ones << i
	return ans % MOD
main()