*A Binod is a person who is very good with bitwise operations. Help Alice solve the following problem and become a Binod.*

You are given an array A of N elements. Process Q queries on this array, of the following form:
Each query contains 5 integers k, L_{1}, R_{1}, L_{2}, R_{2}. It is guaranteed that L_{1} ≤ R_{1} < L_{2} ≤ R_{2}.
The answer to a query is the number of pairs (i, j) such that:
- L_{1} ≤ i ≤ R_{1} and L_{2} ≤ j ≤ R_{2}
- A_{i} \oplus A_{j} has its k-th bit set. Here \oplus denotes the [bitwise XOR] operation.

Note: An integer x is said to have its k-th bit set if the (unique) binary representation of x contains 2^{k}. For example, 5 = 101_{2} = 2^{0} + 2^{2} has its zeroth and second bits set but not the first, while 16 = 10000_{2} = 2^{4} has only its fourth bit set.

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of multiple lines of input.
- The first line of each test case contains two space-separated integers N and Q — the number of elements in array and number of queries, respectively.
- The second line of each test case contains N space-separated integers A_{1}, A_{2}, \ldots, A_{N}.
- The next Q lines describe queries. The i-th of these Q lines contains 5 space-separated integers k, L_{1}, R_{1}, L_{2}, R_{2} — the parameters described in the statement.

------ Output Format ------ 

For each test case, output Q lines.The i-th of these lines should be the answer to the i-th query.

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

$1 ≤ T ≤ 5 \cdot 10^{4}$
$2 ≤ N ≤ 10^{5}$
$1 ≤ Q ≤ 5\cdot 10^{5}$
$0 ≤ A_{i} < 2^{60}$
$1 ≤ L_{1} ≤ R_{1} < L_{2} ≤ R_{2} ≤ N$.
$0 ≤ k < 60$
- The sum of $N$ and $Q$ over all test cases won't exceed $10^{5}$ and $5\cdot 10^{5}$ respectively.

----- Sample Input 1 ------ 
2
5 2
1 2 4 3 2
1 1 3 5 5
2 1 2 3 5
6 2
3 5 6 13 12 20
1 1 4 5 6
3 2 3 4 6

----- Sample Output 1 ------ 
2
2
4
4
----- explanation 1 ------ 
Test case $1$: The array is $A = [1, 2, 4, 3, 2]$.
- Query $1$: the ranges are $[1, 3]$ and $[5, 5]$, and $k = 1$. There are three pairs of $(i, j)$: $(1, 5), (2, 5), (3, 5)$.
- $A_{1} \oplus A_{5} = 1 \oplus 2 = 3 = 11_{2}$ has its first bit set
- $A_{2} \oplus A_{5} = 2 \oplus 2 = 0 = 0_{2}$ doesn't have its first bit set
- $A_{3} \oplus A_{5} = 4 \oplus 2 = 6 = 110_{2}$ has its first bit set
- So, the answer is $2$.
- Query $2$: the ranges are $[1, 2]$ and $[3, 5]$, and now $k = 2$. This time, there are $6$ pairs of indices. Of them, it can be verified that $(1, 3)$ and $(2, 3)$ are the ones that satisfy the given condition.

Difficulty: MEDIUM_HARD
Tags: Range queries

Bit manipulation

Mathematics
Skill types: Bit manipulation

Range queries

Starter code:

Solutions:
for i in range(int(input())):
	(n, q) = input().split()
	n = int(n)
	q = int(q)
	arr = [int(x) for x in input().split()]
	matrix = [[0 for i in range(60)] for j in range(len(arr))]
	for i in range(len(arr)):
		j = 0
		for j in range(60):
			if arr[i] & 1 == 1:
				matrix[i][j] += 1
				if i != 0:
					matrix[i][j] += matrix[i - 1][j]
			else:
				matrix[i][j] += matrix[i - 1][j]
			arr[i] = arr[i] >> 1
	for i in range(q):
		(k, l, r, L, R) = input().split()
		(k, l, r, L, R) = (int(k), int(l) - 1, int(r) - 1, int(L) - 1, int(R) - 1)
		ans1 = 0
		if l != 0:
			ans1 = matrix[r][k] - matrix[l - 1][k]
		else:
			ans1 = matrix[r][k]
		ans2 = r - l + 1 - ans1
		ans3 = matrix[R][k] - matrix[L - 1][k]
		ans4 = R - L + 1 - ans3
		print(ans1 * ans4 + ans2 * ans3)


import sys
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	return input().strip()

def invr():
	return map(int, input().split())

def outp(n):
	sys.stdout.write(str(n) + '\n')

def outlt(lst):
	sys.stdout.write(' '.join(map(str, lst)) + '\n')

def outplt(lst):
	sys.stdout.write('\n'.join(map(str, lst)))

def outpltlt(lst):
	sys.stdout.write('\n'.join(map(str, (' '.join(map(str, a)) for a in lst))))

def prepare(N, A, ma):
	mat = [[0] * (ma + 1) for x in range(N)]
	M = [2 ** x for x in range(ma + 1)]
	for (i, a) in enumerate(A):
		for (j, m) in enumerate(M):
			mat[i][j] = mat[i - 1][j] + bool(a & m)
	return mat

def solve(N, mat, k, l1, r1, l2, r2):
	(o1, o2) = (mat[r1 - 1][k] - (mat[l1 - 2][k] if l1 > 1 else 0), mat[r2 - 1][k] - (mat[l2 - 2][k] if l2 > 1 else 0))
	(z1, z2) = (r1 - l1 + 1 - o1, r2 - l2 + 1 - o2)
	return z1 * o2 + z2 * o1
ans = []
for _ in range(inp()):
	(N, Q) = inlt()
	A = inlt()
	ma = len(bin(max(A))[2:])
	mat = prepare(N, A, ma)
	for q in range(Q):
		(k, l1, r1, l2, r2) = inlt()
		if k > ma:
			an = 0
		else:
			an = solve(N, mat, k, l1, r1, l2, r2)
		ans.append(an)
outplt(ans)


def solve():
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	p = []
	for i in range(60):
		p.append([0] * (n + 1))
	d = 1
	for j in range(60):
		for i in range(n):
			p[j][i + 1] = p[j][i] + (1 if a[i] & d > 0 else 0)
		d *= 2
	for _q in range(q):
		(k, l1, r1, l2, r2) = map(int, input().split())
		p1 = p[k][r1] - p[k][l1 - 1]
		p2 = p[k][r2] - p[k][l2 - 1]
		r = p1 * (r2 - l2 + 1 - p2) + p2 * (r1 - l1 + 1 - p1)
		print(r)
t = 1
t = int(input())
for _test_ in range(t):
	solve()


t = int(input())
for i in range(t):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	zeros = [[0 for di in range(n + 1)] for dj in range(60)]
	ones = [[0 for ci in range(n + 1)] for cj in range(60)]
	for bi in range(1, n + 1):
		bf = bin(a[bi - 1])[::-1]
		for bj in range(60):
			if bj >= len(bf) - 2:
				zeros[bj][bi] = zeros[bj][bi - 1] + 1
				ones[bj][bi] = ones[bj][bi - 1]
			else:
				if bf[bj] == '1':
					ones[bj][bi] = ones[bj][bi - 1] + 1
					zeros[bj][bi] = zeros[bj][bi - 1]
				if bf[bj] == '0':
					zeros[bj][bi] = zeros[bj][bi - 1] + 1
					ones[bj][bi] = ones[bj][bi - 1]
	for j in range(q):
		pairs = 0
		(k, l1, r1, l2, r2) = map(int, input().split())
		z1 = zeros[k][r1] - zeros[k][l1 - 1]
		o1 = ones[k][r1] - ones[k][l1 - 1]
		z2 = zeros[k][r2] - zeros[k][l2 - 1]
		o2 = ones[k][r2] - ones[k][l2 - 1]
		pairs = z1 * o2 + z2 * o1
		print(pairs)


import sys
input = sys.stdin.readline
T = int(input())
for _ in range(T):
	(n, q) = map(int, input().split())
	A = list(map(int, input().split()))
	DP = [[0 for i in range(n)] for j in range(61)]
	for i in range(n):
		val = A[i]
		for j in range(61):
			if val & 1 << j:
				DP[j][i] = 1
			if i != 0:
				DP[j][i] += DP[j][i - 1]
	for i in range(q):
		(k, l1, r1, l2, r2) = map(int, input().split())
		l1 -= 1
		l2 -= 1
		r1 -= 1
		r2 -= 1
		cnt1 = DP[k][r1] - DP[k][l1 - 1]
		cnt2 = DP[k][r2] - DP[k][l2 - 1]
		if l1 == 0:
			cnt1 = DP[k][r1]
		if l2 == 0:
			cnt2 = DP[k][r2]
		ans = cnt1 * (r2 - l2 + 1 - cnt2) + cnt2 * (r1 - l1 + 1 - cnt1)
		print(ans)


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	pref = [[0 for i in range(60)] for _ in range(n + 1)]
	for i in range(n):
		for k in range(60):
			pref[i + 1][k] = pref[i][k] + (a[i] >> k & 1)
	for i in range(q):
		(k, l1, r1, l2, r2) = map(int, input().split())
		(on1, on2) = (pref[r1][k] - pref[l1 - 1][k], pref[r2][k] - pref[l2 - 1][k])
		(off1, off2) = (r1 - l1 + 1 - on1, r2 - l2 + 1 - on2)
		print(on1 * off2 + on2 * off1)


T = int(input())
for i in range(T):
	(Nlen, Query) = map(int, input().split())
	Alist = list(map(int, input().split()))
	prefixlist = [[0] * 60 for i in range(Nlen + 1)]
	for i in range(1, Nlen + 1):
		for k in range(60):
			prefixlist[i][-k - 1] = prefixlist[i - 1][-k - 1] + Alist[i - 1] % 2
			Alist[i - 1] //= 2
	for i in range(Query):
		(k, l1, r1, l2, r2) = map(int, input().split())
		(s1, s2) = (prefixlist[r1][-k - 1] - prefixlist[l1 - 1][-k - 1], prefixlist[r2][-k - 1] - prefixlist[l2 - 1][-k - 1])
		(u1, u2) = (r1 - l1 + 1 - s1, r2 - l2 + 1 - s2)
		print(s1 * u2 + s2 * u1)


for i in range(int(input())):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	pre = [[0] * 60 for i in range(n + 1)]
	for i in range(1, n + 1):
		for k in range(60):
			pre[i][-k - 1] = pre[i - 1][-k - 1] + a[i - 1] % 2
			a[i - 1] //= 2
	for i in range(q):
		(k, l1, r1, l2, r2) = map(int, input().split())
		s1 = pre[r1][-k - 1] - pre[l1 - 1][-k - 1]
		s2 = pre[r2][-k - 1] - pre[l2 - 1][-k - 1]
		u1 = r1 - l1 + 1 - s1
		u2 = r2 - l2 + 1 - s2
		print(s1 * u2 + s2 * u1)


t = int(input())
for _ in range(t):
	(N, Q) = map(int, input().split())
	a = list(map(int, input().split()))
	pre = [[0] * 60 for i in range(N + 1)]
	for i in range(1, N + 1):
		for k in range(60):
			pre[i][-k - 1] = pre[i - 1][-k - 1] + a[i - 1] % 2
			a[i - 1] //= 2
	for i in range(Q):
		(k, l1, r1, l2, r2) = map(int, input().split())
		s1 = pre[r1][-k - 1] - pre[l1 - 1][-k - 1]
		s2 = pre[r2][-k - 1] - pre[l2 - 1][-k - 1]
		u1 = r1 - l1 + (1 - s1)
		u2 = r2 - l2 + (1 - s2)
		print(s1 * u2 + s2 * u1)


BITS = 60

class Numbers:

	def __init__(self, numbers):
		self.numbers = numbers
		self.ac = [[0] * BITS for _ in range(len(numbers))]
		previous = [0] * BITS
		for (i, number) in enumerate(numbers):
			for k in range(BITS):
				self.ac[i][k] = previous[k] + (1 if number & 1 << k else 0)
				previous[k] = self.ac[i][k]

	def query(self, k, l1, r1, l2, r2):
		ones1 = self.ones(l1, r1, k)
		zeros1 = r1 - l1 + 1 - ones1
		ones2 = self.ones(l2, r2, k)
		zeros2 = r2 - l2 + 1 - ones2
		return ones1 * zeros2 + ones2 * zeros1

	def ones(self, l, r, k):
		s2 = self.ac[r - 1][k]
		if l == 1:
			return s2
		else:
			s1 = self.ac[l - 2][k]
			return s2 - s1
for _ in range(int(input())):
	(_, q) = map(int, input().split())
	numbers = Numbers([int(x) for x in input().split()])
	for _ in range(q):
		(k, l1, r1, l2, r2) = map(int, input().split())
		print(numbers.query(k, l1, r1, l2, r2))


def ans(l):
	n = len(l)
	z = [[0 for i in range(61)] for j in range(len(l) + 1)]
	for i in range(len(l)):
		for j in range(61):
			z[i + 1][j] = z[i][j] + (l[i] >> j) % 2
	return z
t = int(input())
for _ in range(t):
	(a, b) = map(int, input().split())
	l = list(map(int, input().split()))
	f = ans(l)
	for i in range(b):
		q = list(map(int, input().split()))
		k = q[0]
		m = f[q[2]][k] - f[q[1] - 1][k]
		n = f[q[4]][k] - f[q[3] - 1][k]
		we = (q[2] - q[1] + 1 - m) * n + m * (q[4] - q[3] + 1 - n)
		print(we)


def preprocess(n):
	prep = [[0] * 60 for _ in range(len(n) + 1)]
	for i in range(len(n)):
		for j in range(60):
			prep[i + 1][j] = prep[i][j]
			if n[i] >> j & 1 == 1:
				prep[i + 1][j] += 1
	return prep

def solve(prep, q):
	toti = q[2] - q[1] + 1
	totj = q[4] - q[3] + 1
	counti = prep[q[2]][q[0]] - prep[q[1] - 1][q[0]]
	countj = prep[q[4]][q[0]] - prep[q[3] - 1][q[0]]
	return counti * totj - 2 * countj * counti + countj * toti

def chset(n, k):
	if n & 1 << k:
		return 1
	return 0
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	n = list(map(int, input().split()))
	prep = preprocess(n)
	for __ in range(q):
		print(solve(prep, list(map(int, input().split()))))


T = int(input())
for _ in range(T):
	(N, Q) = map(int, input().split())
	L = list(map(int, input().split()))
	isSet = [[0] * 60 for _ in range(N + 1)]
	for i in range(N):
		for j in range(60):
			isSet[i + 1][j] = isSet[i][j]
			if L[i] >> j & 1 == 1:
				isSet[i + 1][j] += 1
	for _ in range(Q):
		(k, l1, r1, l2, r2) = map(int, input().split())
		(on1, on2) = (isSet[r1][k] - isSet[l1 - 1][k], isSet[r2][k] - isSet[l2 - 1][k])
		(off1, off2) = (r1 - l1 + 1 - on1, r2 - l2 + 1 - on2)
		print(on1 * off2 + on2 * off1)


def printf(condition):
	if condition:
		print('YES')
	else:
		print('NO')

def solve():
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	pref = [[0 for i in range(60)] for _ in range(n + 1)]
	for i in range(n):
		for k in range(60):
			pref[i + 1][k] = pref[i][k] + (a[i] >> k & 1)
	for i in range(q):
		(k, l1, r1, l2, r2) = map(int, input().split())
		(on1, on2) = (pref[r1][k] - pref[l1 - 1][k], pref[r2][k] - pref[l2 - 1][k])
		(off1, off2) = (r1 - l1 + 1 - on1, r2 - l2 + 1 - on2)
		print(on1 * off2 + on2 * off1)
for _ in range(int(input())):
	solve()


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	m = [int(i) for i in input().split()]
	l = []
	lx = []
	for i in range(n):
		z = [0] * 60
		l.append(z)
		z1 = [0] * 60
		lx.append(z1)
	for i in range(n):
		k = 0
		j = m[i]
		while j:
			if j & 1:
				l[i][k] = 1
				lx[i][k] = 1
			j = j >> 1
			k += 1
	for i in range(1, n):
		for j in range(60):
			l[i][j] += l[i - 1][j]
	for i in range(q):
		(k, l1, r1, l2, r2) = map(int, input().split())
		x = l[r1 - 1][k] - l[l1 - 1][k] + lx[l1 - 1][k]
		y = l[r2 - 1][k] - l[l2 - 1][k] + lx[l2 - 1][k]
		nx = r1 - l1 + 1 - x
		ny = r2 - l2 + 1 - y
		print(x * ny + y * nx)


def isKthSet(n: int, k: int):
	return int(bool(n & 1 << k))
t = int(input())
for _ in range(t):
	(n, q) = map(int, input().split())
	arr = list(map(int, input().split()))
	c1 = []
	for i in range(60):
		l = [0]
		for j in range(n):
			l.append(l[-1] + isKthSet(arr[j], i))
		c1.append(l)
	for __ in range(q):
		(k, l1, r1, l2, r2) = map(int, input().split())
		c1a = c1[k][r1] - c1[k][l1 - 1]
		c1b = c1[k][r2] - c1[k][l2 - 1]
		c0a = r1 - l1 + 1 - c1a
		c0b = r2 - l2 + 1 - c1b
		print(c1a * c0b + c0a * c1b)


for _ in range(int(input())):
	(msn, msq) = map(int, input().split())
	msl = list(map(int, input().split()))
	bit_count = [[0] * 60 for __ in range(msn + 1)]
	for i in range(1, msn + 1):
		num = msl[i - 1]
		for j in range(60):
			bit_count[i][j] = bit_count[i - 1][j] + (num >> j & 1)
	for q in range(msq):
		(k, l1, r1, l2, r2) = map(int, input().split())
		ons1 = bit_count[r1][k] - bit_count[l1 - 1][k]
		zero1 = abs(r1 - l1 + 1 - ons1)
		ons2 = bit_count[r2][k] - bit_count[l2 - 1][k]
		zero2 = abs(r2 - l2 + 1 - ons2)
		print(zero1 * ons2 + ons1 * zero2)


power = [pow(2, i) for i in range(60)]
t = int(input())
for T in range(t):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	pre = [[0 for j in range(n)] for i in range(60)]
	for i in range(n):
		for j in range(60):
			if a[i] & power[j] > 0:
				pre[j][i] = 1
	for i in range(60):
		for j in range(1, n):
			pre[i][j] += pre[i][j - 1]
	for i in range(q):
		(k, l1, r1, l2, r2) = map(int, input().split())
		count1 = pre[k][r1 - 1] - pre[k][l1 - 1]
		count2 = pre[k][r2 - 1] - pre[k][l2 - 1]
		if a[l1 - 1] & power[k] > 0:
			count1 += 1
		if a[l2 - 1] & power[k] > 0:
			count2 += 1
		ans = count1 * (r2 - l2 + 1 - count2) + count2 * (r1 - l1 + 1 - count1)
		print(ans)


for i in range(int(input())):
	(n, q) = map(int, input().split())
	l = list(map(int, input().split()))
	b = [0] * 60
	d = {}
	d[0] = [0] * 60
	j = 1
	for i in l:
		b1 = bin(i)[2:][::-1]
		for i in range(len(b1)):
			if b1[i] == '1':
				b[i] += 1
		b2 = b.copy()
		d[j] = b2
		del b2
		j += 1
	for i in range(q):
		(k, l1, r1, l2, r2) = map(int, input().split())
		ones1 = d[r1][k] - d[l1 - 1][k]
		zero1 = r1 - l1 - ones1 + 1
		ones2 = d[r2][k] - d[l2 - 1][k]
		zero2 = r2 - l2 - ones2 + 1
		print(ones1 * zero2 + ones2 * zero1)


import sys
import math
import bisect
import heapq
from sys import stdin, stdout
from math import gcd, floor, sqrt, log
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
from functools import cmp_to_key
sys.setrecursionlimit(100000000)
inp = lambda : int(input())
strng = lambda : input().strip()
jn = lambda x, l: x.join(map(str, l))
strl = lambda : list(input().strip())
mul = lambda : map(int, stdin.readline().strip().split())
mulf = lambda : map(float, input().strip().split())
seq = lambda : list(map(int, stdin.readline().strip().split()))
ceil = lambda x: int(x) if x == int(x) else int(x) + 1
ceildiv = lambda x, d: x // d if x % d == 0 else x // d + 1
flush = lambda : stdout.flush()
stdstr = lambda : stdin.readline()
stdint = lambda : int(stdin.readline())
stdpr = lambda x: stdout.write(str(x))
sort = lambda x, compare: sorted(x, key=cmp_to_key(compare))
mod = 1000000007

def sumMod(a, b):
	return (a % mod + b % mod) % mod
for _ in range(stdint()):
	(n, q) = mul()
	nums = seq()
	arr = [[0 for j in range(n + 1)] for i in range(60)]
	for i in range(n):
		num = nums[i]
		k = 0
		while num >> k:
			arr[k][i + 1] = num >> k & 1
			k += 1
	for k in range(60):
		for i in range(n):
			arr[k][i + 1] += arr[k][i]
	for i in range(q):
		(k, l1, r1, l2, r2) = mul()
		ones1 = arr[k][r1] - arr[k][l1 - 1]
		zero1 = r1 - l1 + 1 - ones1
		ones2 = arr[k][r2] - arr[k][l2 - 1]
		zero2 = r2 - l2 + 1 - ones2
		print(ones1 * zero2 + zero1 * ones2)


import math
for t in range(int(input())):
	(n, k) = list(map(int, input().split()))
	x = list(map(int, input().split()))
	z = []
	d = []
	s = set()
	for m in range(k):
		y = list(map(int, input().split()))
		z.append(y)
		s.add(y[0])
	for i in range(max(s) + 1):
		p = 2 ** i
		a = 0
		l = list()
		for m in range(n):
			if x[m] // p % 2 == 1:
				a = a + 1
				l.append(a)
			else:
				l.append(a)
		d.append(l)
	for j in range(k):
		if z[j][1] == 1:
			a = d[z[j][0]][z[j][2] - 1]
		else:
			a = d[z[j][0]][z[j][2] - 1] - d[z[j][0]][z[j][1] - 2]
		b = z[j][2] - z[j][1] + 1 - a
		c = d[z[j][0]][z[j][4] - 1] - d[z[j][0]][z[j][3] - 2]
		e = z[j][4] - z[j][3] + 1 - c
		print(a * e + b * c)


for t in range(int(input())):
	(n, q) = [int(i) for i in input().split(' ')]
	a = [int(i) for i in input().split(' ')]
	pre = []
	for i in range(n + 1):
		pre.append([])
		pre[i] = [0 for i in range(64)]
	for i in range(1, n + 1):
		for j in range(64):
			pre[i][j] += pre[i - 1][j]
			if a[i - 1] & 1 << j != 0:
				pre[i][j] += 1
	for _ in range(q):
		(k, l1, r1, l2, r2) = [int(i) for i in input().split(' ')]
		x = pre[r1][k] - pre[l1 - 1][k]
		y = pre[r2][k] - pre[l2 - 1][k]
		c = r1 - l1 + 1
		d = r2 - l2 + 1
		print(x * (d - y) + y * (c - x))


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	d = [[0 for i in range(60)] for j in range(n + 1)]
	for i in range(1, n + 1):
		for j in range(60):
			d[i][j] = d[i - 1][j] + (a[i - 1] >> j & 1)
	for __ in range(q):
		(k, l1, r1, l2, r2) = map(int, input().split())
		setl1r1 = d[r1][k] - d[l1 - 1][k]
		notsetl1r1 = r1 - l1 + 1 - setl1r1
		setl2r2 = d[r2][k] - d[l2 - 1][k]
		notsetl2r2 = r2 - l2 + 1 - setl2r2
		print(setl1r1 * notsetl2r2 + setl2r2 * notsetl1r1)


for i in range(int(input())):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	c = a.copy()
	mp = []
	for f in range(61):
		c[0] = c[0] >> f & 1
		for j in range(1, n):
			c[j] = (c[j] >> f & 1) + c[j - 1]
		mp.append(c)
		c = a.copy()
	for j in range(q):
		(k, l1, r1, l2, r2) = map(int, input().split())
		c = mp[k][l1 - 2]
		if l1 == 1:
			c = 0
		one1 = mp[k][r1 - 1] - c
		zero1 = r1 - l1 - one1 + 1
		one2 = mp[k][r2 - 1] - mp[k][l2 - 2]
		zero2 = r2 - l2 - one2 + 1
		print(zero1 * one2 + one1 * zero2)


def solution(n, q, a, queries):
	dp = [[0 for j in range(n + 1)] for i in range(60)]
	for i in range(n):
		num = a[i]
		k = 0
		while num >> k:
			dp[k][i + 1] = num >> k & 1
			k += 1
	for k in range(60):
		for i in range(n):
			dp[k][i + 1] += dp[k][i]
	for query in queries:
		L1 = query[1]
		R1 = query[2]
		L2 = query[3]
		R2 = query[4]
		bit = query[0]
		leftCountOne = dp[bit][R1] - dp[bit][L1 - 1]
		leftCountZero = R1 - L1 + 1 - leftCountOne
		RightCountOne = dp[bit][R2] - dp[bit][L2 - 1]
		RightCountZero = R2 - L2 + 1 - RightCountOne
		pairs = leftCountOne * RightCountZero + leftCountZero * RightCountOne
		print(pairs)
	return None
for _ in range(int(input())):
	queries = []
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))[:n]
	for i in range(q):
		temp = list(map(int, input().split()))
		queries.append(temp)
	solution(n, q, a, queries)


def soln(n, q, arr, queries):
	n = len(arr)
	dp = [[0] * (n + 1) for _ in range(60)]
	for i in range(60):
		prev = 0
		mask = 1 << i
		for j in range(n):
			if mask & arr[j]:
				prev += 1
				dp[i][j + 1] = prev
			else:
				dp[i][j + 1] = prev
	for (k, l1, r1, l2, r2) in queries:
		ones = dp[k][r1] - dp[k][l1 - 1]
		zeros = r1 - l1 + 1 - ones
		rones = dp[k][r2] - dp[k][l2 - 1]
		rzeros = r2 - l2 + 1 - rones
		res = ones * rzeros + rones * zeros
		print(res)
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	arr = list(map(int, input().split()))
	queries = [list(map(int, input().split())) for i in range(q)]
	soln(n, q, arr, queries)


def prefix(a, n):
	pref = []
	for i in range(61):
		pref.append([])
		for j in range(n):
			tst = a[j] & 1 << i
			if tst:
				pref[i].append(1)
			else:
				pref[i].append(0)
	for i in range(61):
		for j in range(1, n):
			pref[i][j] += pref[i][j - 1]
	return pref

def solve2(qu, pref):
	(l1, r1) = (qu[1], qu[2])
	(l2, r2) = (qu[3], qu[4])
	k = qu[0]
	o1 = pref[k][r1 - 1]
	if l1 - 2 >= 0:
		o1 = o1 - pref[k][l1 - 2]
	z1 = r1 - l1 + 1 - o1
	o2 = pref[k][r2 - 1]
	if l2 - 2 >= 0:
		o2 = o2 - pref[k][l2 - 2]
	z2 = r2 - l2 + 1 - o2
	return o1 * z2 + o2 * z1
t = int(input())
for _ in range(t):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	pref = prefix(a, n)
	for i in range(q):
		qu = list(map(int, input().split()))
		print(solve2(qu, pref))


T = int(input())
for _ in range(T):
	(N, Q) = map(int, input().split())
	A = list(map(int, input().split()))
	ps = [[0] * 60 for i in range(N + 1)]
	for i in range(N):
		for j in range(60):
			ps[i + 1][j] = ps[i][j] + (A[i] >> j & 1)
	for q in range(Q):
		(k, L1, R1, L2, R2) = map(int, input().split())
		ones1 = ps[R1][k] - ps[L1 - 1][k]
		zeros1 = R1 - L1 + 1 - ones1
		ones2 = ps[R2][k] - ps[L2 - 1][k]
		zeros2 = R2 - L2 + 1 - ones2
		print(ones1 * zeros2 + zeros1 * ones2)


from collections import Counter
for _ in range(int(input())):
	(N, Q) = map(int, input().split())
	A = list(map(int, input().split()))
	dp = [[0] * N for _ in range(60)]
	for i in range(60):
		num = 1 << i
		for j in range(N):
			if j == 0:
				if A[j] & num:
					dp[i][j] = 1
				else:
					dp[i][j] = 0
			elif A[j] & num:
				dp[i][j] = dp[i][j - 1] + 1
			else:
				dp[i][j] = dp[i][j - 1]
	for _ in range(Q):
		(k, l1, r1, l2, r2) = map(int, input().split())
		(t1, t2) = (r1 - l1 + 1, r2 - l2 + 1)
		c1 = c2 = 0
		if l1 == 1:
			c1 = dp[k][r1 - 1]
		else:
			c1 = dp[k][r1 - 1] - dp[k][l1 - 2]
		if l2 == 1:
			c2 = dp[k][r2 - 1]
		else:
			c2 = dp[k][r2 - 1] - dp[k][l2 - 2]
		print(c1 * (t2 - c2) + c2 * (t1 - c1))


t = int(input())
for _ in range(t):
	(n, q) = map(int, input().split())
	arr = list(map(int, input().split()))
	prefik = dict()
	for k in range(60):
		setk = 0
		prefik[0, k] = 0
		for i in range(n):
			setk += (arr[i] >> k) % 2
			prefik[i + 1, k] = setk
	for _ in range(q):
		(k, l1, r1, l2, r2) = map(int, input().split())
		ans = (prefik[r1, k] - prefik[l1 - 1, k]) * (r2 - l2 + 1 - (prefik[r2, k] - prefik[l2 - 1, k])) + (prefik[r2, k] - prefik[l2 - 1, k]) * (r1 - l1 + 1 - (prefik[r1, k] - prefik[l1 - 1, k]))
		print(ans)


def main():
	t = int(input())
	for _ in range(t):
		(n, q) = map(int, input().split())
		l = [int(x) for x in input().split()]
		a = [[0 for i in range(n + 1)] for j in range(61)]
		for i in range(61):
			for j in range(1, n + 1):
				if (l[j - 1] >> i) % 2 == 1:
					a[i][j] = a[i][j - 1] + 1
				else:
					a[i][j] = a[i][j - 1]
		for i in range(q):
			(k, l1, r1, l2, r2) = map(int, input().split())
			ro = a[k][r1] - a[k][l1 - 1]
			rz = r1 - l1 - ro + 1
			lo = a[k][r2] - a[k][l2 - 1]
			lz = r2 - l2 - lo + 1
			print(ro * lz + rz * lo)
main()


def checkbit(n, i):
	if n >> i & 1 == 1:
		return True
	return False
t = int(input())
for _ in range(t):
	(n, q) = map(int, input().split())
	l = []
	arr = list(map(int, input().split()))
	for i in range(60):
		l1 = []
		l1.append(0)
		s = 0
		for j in range(n):
			if checkbit(arr[j], i) == 1:
				s = s + 1
			l1.append(s)
		l.append(l1)
	for __ in range(q):
		(k, l1, r1, l2, r2) = map(int, input().split())
		x1 = l[k][r1] - l[k][l1 - 1]
		x0 = r1 - l1 + 1 - x1
		y1 = l[k][r2] - l[k][l2 - 1]
		y0 = r2 - l2 + 1 - y1
		print(x1 * y0 + x0 * y1)


R = lambda : map(int, input().split())
(t,) = R()
for _ in range(t):
	(n, q) = R()
	a = [[0] * (n + 1) for _ in range(60)]
	for (i, x) in enumerate(R()):
		for (j, b) in enumerate(a):
			b[i + 1] = b[i] + (x >> j & 1)
	for _ in range(q):
		(k, l1, r1, l2, r2) = R()
		l1 -= 1
		l2 -= 1
		b = a[k]
		((d1, c1), (d2, c2)) = ((r - l, b[r] - b[l]) for (r, l) in ((r1, l1), (r2, l2)))
		print(c1 * (d2 - c2) + (d1 - c1) * c2)


def binary(n):
	ans = ''
	count = 0
	while n > 0:
		ans += str(n % 2)
		count += 1
		n = n // 2
	return (64 - count) * '0' + ans[::-1]
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	lst = list(map(int, input().split()))
	binary_lst = [0] * n
	grand_count_zero_lst = []
	grand_count_one_lst = []
	for i in range(n):
		binary_lst[i] = binary(lst[i])
	for j in range(64):
		count_zero = 0
		count_one = 0
		count_zero_lst = []
		count_one_lst = []
		for i in range(n):
			if binary_lst[i][j] == '0':
				count_zero += 1
			else:
				count_one += 1
			count_zero_lst.append(count_zero)
			count_one_lst.append(count_one)
		grand_count_zero_lst.append([0] + count_zero_lst)
		grand_count_one_lst.append([0] + count_one_lst)
	for i in range(q):
		(k, l1, r1, l2, r2) = map(int, input().split())
		var_1 = (grand_count_zero_lst[64 - k - 1][r1] - grand_count_zero_lst[64 - k - 1][l1 - 1]) * (grand_count_one_lst[64 - k - 1][r2] - grand_count_one_lst[64 - k - 1][l2 - 1])
		var_2 = (grand_count_one_lst[64 - k - 1][r1] - grand_count_one_lst[64 - k - 1][l1 - 1]) * (grand_count_zero_lst[64 - k - 1][r2] - grand_count_zero_lst[64 - k - 1][l2 - 1])
		print(var_1 + var_2)


for t in range(int(input())):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	check = [[0 for i in range(60)] for j in range(n + 1)]
	for i in range(n):
		for j in range(60):
			check[i + 1][j] = check[i][j] + (a[i] >> j & 1)
	for x in range(q):
		(k, l1, r1, l2, r2) = map(int, input().split())
		(o1, o2) = (check[r1][k] - check[l1 - 1][k], check[r2][k] - check[l2 - 1][k])
		(z1, z2) = (r1 - l1 + 1 - o1, r2 - l2 + 1 - o2)
		print(o1 * z2 + o2 * z1)


import sys
from collections import defaultdict as dd, deque
input = lambda : sys.stdin.readline().strip()

def ii():
	return int(input())

def ia():
	return list(map(int, input().split()))
INF = float('inf')
MOD = 10 ** 9 + 7
g4 = [(0, 1), (0, -1), (1, 0), (-1, 0)]
g8 = [(0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (-1, -1), (1, -1), (-1, 1)]
t = ii()
for _ in range(t):
	(n, q) = ia()
	a = ia()
	ar = [[0] * 62 for _ in range(n)]
	for i in range(n):
		for j in range(62):
			if a[i] & 1 << j:
				ar[i][j] = 1
	for i in range(1, n):
		for j in range(62):
			ar[i][j] += ar[i - 1][j]
	ar = [[0] * 62] + ar
	for _ in range(q):
		(k, l1, r1, l2, r2) = ia()
		z1 = ar[r1][k] - ar[l1 - 1][k]
		z2 = ar[r2][k] - ar[l2 - 1][k]
		print(z1 * (r2 - l2 + 1 - z2) + z2 * (r1 - l1 + 1 - z1))


t = int(input())
for _ in range(t):
	(n, q) = map(int, input().split())
	arr = list(map(int, input().split()))
	pf = [[0] for _ in range(60)]
	for i in range(n):
		for b in range(60):
			if arr[i] & 1 << b:
				pf[b].append(pf[b][-1] + 1)
			else:
				pf[b].append(pf[b][-1])
	for _ in range(q):
		res = 0
		(k, l1, r1, l2, r2) = map(int, input().split())
		xctr = r1 - l1 + 1
		yctr = r2 - l2 + 1
		x = pf[k][r1] - pf[k][l1 - 1]
		y = pf[k][r2] - pf[k][l2 - 1]
		print(x * (yctr - y) + y * (xctr - x))


import sys
input = sys.stdin.readline

def main():
	for testcases in range(int(input())):
		(n, q) = map(int, input().split())
		array = list(map(int, input().split()))
		prefk = [[] for _ in range(60)]
		for k in range(60):
			for i in range(n):
				bitset = array[i] >> k & 1
				if i == 0:
					prefk[k].append(bitset)
				else:
					prefk[k].append(prefk[k][-1] + bitset)
		for _ in range(q):
			(k, l1, r1, l2, r2) = map(int, input().split())
			S1 = prefk[k][r1 - 1] - prefk[k][l1 - 2] if l1 - 1 != 0 else prefk[k][r1 - 1]
			U1 = r1 - l1 + 1 - S1
			S2 = prefk[k][r2 - 1] - prefk[k][l2 - 2]
			U2 = r2 - l2 + 1 - S2
			print(S1 * U2 + S2 * U1)
main()


def KthBit(n, k):
	if n < 2 ** k:
		return 0
	else:
		k += 1
		return (n & 1 << k - 1) >> k - 1
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	z = lambda x: bin(int(x))[2:]
	arr = list(map(int, input().split()))
	pre = []
	for i in range(60):
		temp = [0]
		p = 0
		for j in arr:
			p += KthBit(j, i)
			temp.append(p)
		pre.append(temp)
	for i in range(q):
		(k, L1, R1, L2, R2) = map(int, input().split())
		o1 = pre[k][R1] - pre[k][L1 - 1]
		o2 = pre[k][R2] - pre[k][L2 - 1]
		ans = o1 * (R2 - L2 - o2 + 1) + o2 * (R1 - L1 - o1 + 1)
		print(ans)


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	A = list(map(int, input().split()))
	d = {}
	for i in range(0, 60):
		t0 = [0]
		t1 = [0]
		for a in A:
			if a & 2 ** i == 0:
				t0.append(t0[-1] + 1)
				t1.append(t1[-1] + 0)
			else:
				t0.append(t0[-1] + 0)
				t1.append(t1[-1] + 1)
		d[i] = [t0, t1]
	for _ in range(q):
		(k, l1, r1, l2, r2) = map(int, input().split())
		t0 = d[k][0]
		t1 = d[k][1]
		x0 = t0[r1] - t0[l1 - 1]
		x1 = t1[r1] - t1[l1 - 1]
		y0 = t0[r2] - t0[l2 - 1]
		y1 = t1[r2] - t1[l2 - 1]
		print(x0 * y1 + y0 * x1)


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	l = [int(x) for x in input().split()]
	ans = []
	for i in range(60):
		x = []
		s = 0
		for j in range(n):
			if 1 << i & l[j]:
				s += 1
			x.append(s)
		ans.append(x)
	for i in range(q):
		(k, l1, r1, l2, r2) = map(int, input().split())
		if l1 != 1:
			c1 = ans[k][r1 - 1] - ans[k][l1 - 2]
		else:
			c1 = ans[k][r1 - 1]
		c2 = r1 - l1 + 1 - c1
		if l2 != 1:
			d1 = ans[k][r2 - 1] - ans[k][l2 - 2]
		else:
			d1 = ans[k][r2 - 1]
		d2 = r2 - l2 + 1 - d1
		print(c1 * d2 + c2 * d1)


t = int(input())
while t > 0:
	(n, q) = input().split()
	q = int(q)
	Arr = [int(x) for x in input().split()]
	m = max(Arr)
	msb = 0
	for i in range(31, 0, -1):
		if m >> i & 1 == 1:
			msb = i
			break
	temp = [[0 for _ in range(60)]]
	for i in Arr:
		te = [0 for _ in range(60)]
		for sh in range(60):
			if i >> sh & 1 == 1:
				te[sh] = temp[-1][sh] + 1
			else:
				te[sh] = temp[-1][sh]
		temp.append(te)
	temp = temp[1:]
	for _ in range(q):
		i_cnt_0 = 0
		i_cnt_1 = 0
		j_cnt_0 = 0
		j_cnt_1 = 0
		l = [int(x) for x in input().split()]
		if l[2] - 1 >= len(temp):
			x = temp[-1][l[0]]
		else:
			x = temp[l[2] - 1][l[0]]
		y = 0
		if l[1] - 2 >= 0:
			y = temp[l[1] - 2][l[0]]
		i_cnt_1 = x - y
		i_cnt_0 = l[2] - l[1] + 1 - i_cnt_1
		if l[4] - 1 >= len(temp):
			x = temp[-1][l[0]]
		else:
			x = temp[l[4] - 1][l[0]]
		y = 0
		if l[3] - 2 >= 0:
			y = temp[l[3] - 2][l[0]]
		j_cnt_1 = x - y
		j_cnt_0 = l[4] - l[3] + 1 - j_cnt_1
		ans = 0
		ans += i_cnt_0 * j_cnt_1
		ans += i_cnt_1 * j_cnt_0
		print(ans)
	t -= 1


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	d = {}
	for i in range(60):
		t0 = [0]
		t1 = [0]
		for j in a:
			if j & 2 ** i == 0:
				t0.append(t0[-1] + 1)
				t1.append(t1[-1] + 0)
			else:
				t0.append(t0[-1] + 0)
				t1.append(t1[-1] + 1)
		d[i] = [t0, t1]
	for t in range(q):
		(k, l1, r1, l2, r2) = map(int, input().split())
		t0 = d[k][0]
		t1 = d[k][1]
		i0 = t0[r1] - t0[l1 - 1]
		i1 = t1[r1] - t1[l1 - 1]
		j0 = t0[r2] - t0[l2 - 1]
		j1 = t1[r2] - t1[l2 - 1]
		print(i0 * j1 + i1 * j0)


for _ in range(int(input())):
	a = list(map(int, input().split()))
	l = list(map(int, input().split()))
	re = []
	for i in range(62):
		r = []
		d = 0
		for j in l:
			if j & 1 << i:
				d += 1
			r.append(d)
		re.append(r)
	for i in range(a[1]):
		k = list(map(int, input().split()))
		res = re[k[0]]
		if k[1] == 1:
			a = res[k[2] - 1]
		else:
			a = res[k[2] - 1] - res[k[1] - 2]
		b = k[2] - k[1] + 1 - a
		if k[3] == 1:
			c = res[k[4] - 1]
		else:
			c = res[k[4] - 1] - res[k[3] - 2]
		d = k[4] - k[3] + 1 - c
		print(a * d + b * c)


def toBin(n):
	return bin(n).replace('0b', '')

def isValid(num, k):
	st = toBin(num)
	st = list(st)
	st = st[::-1]
	if k < len(st) and st[k] == '1':
		return True
	return False
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	nums = list(map(int, input().split()))
	arr = [[0 for i in range(n)] for j in range(64)]
	for i in range(n):
		num = nums[i]
		for j in range(64):
			arr[j][i] = int(num % 2)
			num = num // 2
	for i in range(64):
		flg = 0
		for j in range(n):
			flg += arr[i][j]
			arr[i][j] = flg
	for __ in range(q):
		(k, l1, r1, l2, r2) = map(int, input().split())
		(pairs, seen) = (0, set())
		pair1 = arr[k][r1 - 1] if l1 == 1 else arr[k][r1 - 1] - arr[k][l1 - 2]
		pair2 = arr[k][r2 - 1] if l2 == 1 else arr[k][r2 - 1] - arr[k][l2 - 2]
		totalPairs = (r1 - l1 + 1 - pair1) * pair2 + (r2 - l2 + 1 - pair2) * pair1
		print(totalPairs)


for i in range(int(input())):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	bits = [0] * 60
	f = []
	for s in a:
		for j in range(60):
			if s & 2 ** j == 2 ** j:
				bits[j] += 1
		k = bits.copy()
		f.append(k)
	for j in range(q):
		(k, l1, r1, l2, r2) = map(int, input().split())
		ones1 = f[r1 - 1][k] - f[l1 - 1][k]
		if l1 != 1 and f[l1 - 2][k] != f[l1 - 1][k]:
			ones1 += 1
		if l1 == 1 and f[l1 - 1][k] == 1:
			ones1 += 1
		ones2 = f[r2 - 1][k] - f[l2 - 1][k]
		if f[l2 - 2][k] != f[l2 - 1][k]:
			ones2 += 1
		zero1 = r1 - l1 + 1 - ones1
		zero2 = r2 - l2 + 1 - ones2
		print(ones1 * zero2 + ones2 * zero1)