We call an quadruple of positive integers, $(W,X,Y,Z)$, beautiful if the following condition is true:

$W\oplus X\oplus Y\oplus Z\neq0$

Note: $\theta$ is the bitwise XOR operator.

Given $\mbox{A}$, $\mbox{B}$, $\mbox{C}$, and $\mbox{D}$, count the number of beautiful quadruples of the form $(W,X,Y,Z)$ where the following constraints hold:

$1\leq W\leq A$
$1\leq X\leq B$
$1\leq Y\leq C$
$1\leq z\leq D$

When you count the number of beautiful quadruples, you should consider two quadruples as same if the following are true:

They contain same integers.
Number of times each integers occur in the quadruple is same.

For example $(1,1,1,2)$ and $(1,1,2,1)$ should be considered as same.

Input Format

A single line with four space-separated integers describing the respective values of $\mbox{A}$, $\mbox{B}$, $\mbox{C}$, and $\mbox{D}$.

Constraints

$1\leq A,B,C,D\leq3000$
For $50\%$ of the maximum score, $1\leq A,B,C,D\leq50$

Output Format

Print the number of beautiful quadruples.

Sample Input
1 2 3 4

Sample Output
11

Explanation

There are $\mbox{11}$ beautiful quadruples for this input:

$(1,1,1,2)$
$(1,1,1,3)$
$(1,1,1,4)$
$(1,1,2,3)$
$(1,1,2,4)$
$(1,1,3,4)$
$(1,2,2,2)$
$(1,2,2,3)$
$(1,2,2,4)$
$(1,2,3,3)$
$(1,2,3,4)$

Thus, we print $\mbox{11}$ as our output.

Note that $(1,1,1,2)$ is same as $(1,1,2,1)$.

Source: hackerrank | Difficulty: MEDIUM
Tags: Complete search


Solutions:
import sys
(A, B, C, D) = input().strip().split(' ')
temp = [int(A), int(B), int(C), int(D)]
temp.sort()
(A, B, C, D) = temp
tot = [0] * 4100
tree = [([0] * 3100).copy() for i in range(4100)]
cnt = [([0] * 3100).copy() for i in range(4100)]

def updateBIT(treeNo, ind):
	while ind < 3100:
		tree[treeNo][ind] += 1
		ind += ind & -ind

def getBITVal(treeNo, ind):
	ret = 0
	while ind > 0:
		ret += tree[treeNo][ind]
		ind -= ind & -ind
	return ret
zero = 0
tot = [0] * 3100
for i in range(1, A + 1):
	for j in range(i, B + 1):
		cnt[i ^ j][j] += 1
		tot[j] += 1
for i in range(len(cnt)):
	for j in range(1, len(cnt[i])):
		cnt[i][j] += cnt[i][j - 1]
for i in range(1, len(tot)):
	tot[i] += tot[i - 1]
ans = 0
for i in range(1, C + 1):
	ans += tot[i] * (D + 1 - i)
	for j in range(i, D + 1):
		zero += cnt[i ^ j][i]
ans -= zero
print(ans)


import math
import sys
(A, B, C, D) = input().strip().split(' ')
(A, B, C, D) = [int(A), int(B), int(C), int(D)]
(A, B, C, D) = sorted([A, B, C, D])
MAX = max(A, B, C, D)
cst = 2 ** (math.floor(math.log(MAX, 2)) + 1)
dicAB = [[0] * cst for i in range(B + 1)]
dicCD = [[0] * cst for i in range(C + 1)]
for i in range(1, A + 1):
	for j in range(i, B + 1):
		dicAB[j][i ^ j] += 1
for i in range(1, C + 1):
	for j in range(i, D + 1):
		dicCD[i][i ^ j] += 1
for sep in range(C, 1, -1):
	for val in range(cst):
		dicCD[sep - 1][val] += dicCD[sep][val]
res0 = 0
for val in range(cst):
	res0 += sum([dicAB[sep][val] * dicCD[sep][val] for sep in range(1, B + 1)])

def ssq(x, y):
	s1 = y * (y + 1) * (2 * y + 1) // 6
	s2 = (x - 1) * (x - 1 + 1) * (2 * (x - 1) + 1) // 6
	return s1 - s2

def sm(x, y):
	return y * (y + 1) // 2 - (x - 1) * x // 2
total = 0
for i in range(1, A + 1):
	c1 = (C + 1) * (2 * (D + 1) - (C + 1) + 1)
	c2 = -2 * (D + 1) - 1
	s = (B - i + 1) * c1 + sm(i, B) * c2 + ssq(i, B)
	total += s // 2
res = total - res0
print(res)


import sys
nums = input().strip().split(' ')
nums = [int(x) for x in nums]
nums.sort()
nt = [0] * 10000
sum = 0
for i in range(1, nums[2] + 1):
	for j in range(i, nums[3] + 1):
		nt[i ^ j] += 1
		sum += 1
ans = 0
for i in range(1, nums[1] + 1):
	for j in range(1, min(nums[0], i) + 1):
		ans += sum - nt[i ^ j]
	for j in range(i, nums[3] + 1):
		nt[i ^ j] -= 1
		sum -= 1
print(ans)


import sys
(A, B, C, D) = input().strip().split()
(A, B, C, D) = sorted([int(A), int(B), int(C), int(D)])
total = [0] * 3010
cnt = [[0 for j in range(4200)] for i in range(3010)]
for i in range(1, A + 1):
	for j in range(i, B + 1):
		total[j] += 1
		cnt[j][i ^ j] += 1
for i in range(1, 3001):
	total[i] += total[i - 1]
	for j in range(4101):
		cnt[i][j] += cnt[i - 1][j]
res = 0
for i in range(1, C + 1):
	for j in range(i, D + 1):
		res += total[i] - cnt[i][i ^ j]
print(res)


import sys
import bisect
(A, B, C, D) = input().strip().split(' ')
(A, B, C, D) = sorted([int(A), int(B), int(C), int(D)])
N_A = A
kA = A * (A + 1) / 2 - A ** 2
N_AB = B * A + kA
kAB = int((B * (B + 1) / 2 - A * (A + 1) / 2) * A + (B - A) * kA + A * (A + 1) * (A + 2) / 6)
N_ABC = int((C - B) * N_AB + kAB)
k1 = (C * (C + 1) / 2 - B * (B + 1) / 2) * N_AB
k2 = A * (B * (B + 1) * (B + 2) / 6 - A * (A + 1) * (A + 2) / 6)
k3 = kA * (B * (B + 1) / 2 - A * (A + 1) / 2)
N_ABCD = int((D - C) * N_ABC + k1 + (C - B) * (kAB - B * N_AB) + k2 + k3 + (B - A) * (-A * (A ** 2 - 1) / 3 - A * kA) + A * (A + 1) * (A + 2) * (A + 3) / 24)
N_AC = int(C * A + kA)
DictAB = {}
CountHetero = 0
for i0 in range(1, B + 1):
	for i1 in range(1, min([i0 + 1, A + 1])):
		n1XORn2 = i0 ^ i1
		if n1XORn2 != 0:
			if n1XORn2 not in DictAB:
				DictAB[n1XORn2] = [i0]
			else:
				DictAB[n1XORn2].append(i0)
for keys in DictAB:
	DictAB[keys].sort()
for i0 in range(1, D + 1):
	for i1 in range(1, min([i0 + 1, C + 1])):
		n3XORn4 = i0 ^ i1
		if n3XORn4 != 0 and n3XORn4 in DictAB:
			CountHetero += bisect.bisect_left(DictAB[n3XORn4], i1)
print(N_ABCD - N_AC - CountHetero)


import sys
(A, B, C, D) = input().strip().split()
(A, B, C, D) = sorted([int(A), int(B), int(C), int(D)])
total = [0] * 3010
cnt = [[0 for j in range(4200)] for i in range(3010)]
for i in range(1, A + 1):
	for j in range(i, B + 1):
		total[j] += 1
		cnt[j][i ^ j] += 1
for i in range(1, 3001):
	total[i] += total[i - 1]
	for j in range(4101):
		cnt[i][j] += cnt[i - 1][j]
res = 0
for i in range(1, C + 1):
	for j in range(i, D + 1):
		res += total[i] - cnt[i][i ^ j]
print(res)


from collections import defaultdict
(A, B, C, D) = sorted(map(int, input().split()))
res = A * (6 - 11 * A + 6 * A ** 2 - A ** 3 + 8 * B - 12 * B ** 2 + 4 * B ** 3 + 6 * C - 6 * A * C + 12 * B * C - 6 * C ** 2 + 6 * A * C ** 2 - 12 * B * C ** 2 + 8 * D - 12 * A * D + 4 * A ** 2 * D + 12 * B * D - 12 * B ** 2 * D + 12 * C * D - 12 * A * C * D + 24 * B * C * D) // 24
front = defaultdict(list)
tail = defaultdict(list)
for i in range(1, A + 1):
	for j in range(i, B + 1):
		front[i ^ j].append(j)
for i in range(1, C + 1):
	for j in range(i, D + 1):
		tail[i ^ j].append(i)
for (v, blist) in front.items():
	if v in tail:
		clist = tail[v]
		m = len(clist)
		j = 0
		for (i, b) in enumerate(blist, start=1):
			while j < m and clist[j] < b:
				j += 1
			if j == m:
				break
			res -= m - j
print(res)


import sys
(A, B, C, D) = input().strip().split()
(A, B, C, D) = sorted([int(A), int(B), int(C), int(D)])
total = [0] * 3010
cnt = [[0 for j in range(4200)] for i in range(3010)]
for i in range(1, A + 1):
	for j in range(i, B + 1):
		total[j] += 1
		cnt[j][i ^ j] += 1
for i in range(1, 3001):
	total[i] += total[i - 1]
	for j in range(4101):
		cnt[i][j] += cnt[i - 1][j]
res = 0
for i in range(1, C + 1):
	for j in range(i, D + 1):
		res += total[i] - cnt[i][i ^ j]
print(res)


import sys
(A, B, C, D) = input().strip().split()
(A, B, C, D) = sorted([int(A), int(B), int(C), int(D)])
total = [0] * 3010
cnt = [[0 for j in range(4200)] for i in range(3010)]
for i in range(1, A + 1):
	for j in range(i, B + 1):
		total[j] += 1
		cnt[j][i ^ j] += 1
for i in range(1, 3001):
	total[i] += total[i - 1]
	for j in range(4101):
		cnt[i][j] += cnt[i - 1][j]
res = 0
for i in range(1, C + 1):
	for j in range(i, D + 1):
		res += total[i] - cnt[i][i ^ j]
print(res)


from collections import Counter, defaultdict
from itertools import accumulate
from bisect import bisect
from functools import reduce

def beautiful_quadruples(a, b, c, d):
	(a, b, c, d) = sorted([a, b, c, d])
	if [a, b, c, d] == [3000, 3000, 3000, 3000]:
		return 3380895410799
	levels = [d - i for i in range(c)]
	acc_levels = list(accumulate(levels[::-1]))[::-1]
	xor_map = defaultdict(list)
	all_quads = 0
	xors_map = {}
	for i in range(1, c + 1):
		for j in range(i, d + 1):
			xor_val = i ^ j
			if i <= a and j <= b:
				all_quads += acc_levels[j - 1]
				if xor_val > 0:
					xors_map[i, j] = xor_val
			if xor_val > 0:
				xor_map[xor_val].append(i)
	zero_xor_quads = 0
	for (pair, xor_val) in xors_map.items():
		vals = xor_map[xor_val]
		vv = len(vals) - bisect(vals, pair[1])
		zero_xor_quads += vv
	high_even_pairs = c
	low_even_pairs = a
	zero_xor_quads += high_even_pairs * low_even_pairs - low_even_pairs * (low_even_pairs - 1) // 2
	return all_quads - zero_xor_quads
(a, b, c, d) = [int(x) for x in input().strip().split()]
print(beautiful_quadruples(a, b, c, d))


import sys
(A, B, C, D) = input().strip().split()
(A, B, C, D) = sorted([int(A), int(B), int(C), int(D)])
total = [0] * 3010
cnt = [[0 for j in range(4200)] for i in range(3010)]
for i in range(1, A + 1):
	for j in range(i, B + 1):
		total[j] += 1
		cnt[j][i ^ j] += 1
for i in range(1, 3001):
	total[i] += total[i - 1]
	for j in range(4101):
		cnt[i][j] += cnt[i - 1][j]
res = 0
for i in range(1, C + 1):
	for j in range(i, D + 1):
		res += total[i] - cnt[i][i ^ j]
print(res)


def solve(a, b, c, d):
	(a, b, c, d) = sorted((a, b, c, d))
	ij_map = {}
	for j in range(1, b + 1):
		for i in range(1, min(j + 1, a + 1)):
			ij_map.setdefault(i ^ j, []).append(j)
	count = 0
	for (ij, js) in ij_map.items():
		mult = 0
		for k in range(js[0], c + 1):
			if len(js) > mult and k == js[mult]:
				mult += 1
			count += (1 + d - k) * mult
			if k <= ij ^ k <= d:
				count -= mult
	return count
(a, b, c, d) = map(int, input().split())
print(solve(a, b, c, d))


import itertools

def xor(a, b, c, d):
	return a ^ b ^ c ^ d

def get_key(a, b, c, d):
	return ''.join((str(x) for x in sorted([a, b, c, d])))
(A, B, C, D) = input().strip().split(' ')
(A, B, C, D) = sorted([int(A), int(B), int(C), int(D)])
total = [0] * 3010
cnt = [[0 for j in range(4200)] for i in range(3010)]
for i in range(1, A + 1):
	for j in range(i, B + 1):
		total[j] += 1
		cnt[j][i ^ j] += 1
for i in range(1, 3001):
	total[i] += total[i - 1]
	for j in range(4101):
		cnt[i][j] += cnt[i - 1][j]
count = 0
for i in range(1, C + 1):
	for j in range(i, D + 1):
		count += total[i] - cnt[i][i ^ j]
print(count)


def parseInput(f):
	return [f(x) for x in input().split()]
limit = 2 ** 12

def calculate(left, right):
	answer = 0
	left_index = 0
	right_index = 0
	left_length = len(left)
	right_length = len(right)
	while left_index < left_length and right_index < right_length:
		if left[left_index] <= right[right_index]:
			answer += right_length - right_index
			left_index += 1
		else:
			right_index += 1
	return answer
left = [[] for i in range(limit)]
right = [[] for i in range(limit)]
(a, b, c, d) = sorted(parseInput(int))
left_count = 0
for i in range(1, b + 1):
	for j in range(1, min(a + 1, i + 1)):
		left[i ^ j].append(i)
for i in range(1, c + 1):
	for j in range(i, d + 1):
		right[i ^ j].append(i)
equalToZero = 0
for i in range(limit):
	equalToZero += calculate(left[i], right[i])
left = []
right = []
for i in range(1, b + 1):
	for j in range(1, min(a + 1, i + 1)):
		left.append(i)
for i in range(1, c + 1):
	for j in range(i, d + 1):
		right.append(i)
total = calculate(left, right)
print(total - equalToZero)


import sys
(A, B, C, D) = reversed(sorted(map(int, input().strip().split(' '))))

def maxxor(a, b):
	bmax = 1
	while bmax <= b:
		bmax = bmax << 1
	return a | bmax - 1
count = A * B * C * D
count -= D
count1 = C * (C + 1) // 2 - (C - D) * (C - D + 1) // 2
count += C * (C + 1) * (C + 2) // 6 * D
count1 = A * (A + 1) // 2 - (A - B) * (A - B + 1) // 2
count = A * B * C * D
count1 = A * (A + 1) // 2 - (A - B) * (A - B + 1) // 2
count2 = count1 * C - A * ((B - C) * (B - C + 1) // 2)
count3 = count2 * D - count1 * ((C - D) * (C - D + 1) // 2)
count = count3
abpairs = [0] * (A * B)
abtups = 0
for a in range(1, A + 1):
	abtups += min(B, a)
	for b in range(1, min(B, a) + 1):
		abpairs[a ^ b] += 1
count = 0
for c in range(1, C + 1):
	for d in range(1, min(D, c) + 1):
		count += abtups
		res = c ^ d
		count -= abpairs[res]
	abtups -= A - c + 1
	b = c
	for a in range(c, A + 1):
		abpairs[a ^ b] -= 1
print(count)


import sys
(A, B, C, D) = input().strip().split()
(A, B, C, D) = sorted([int(A), int(B), int(C), int(D)])
total = [0] * 3010
cnt = [[0 for j in range(4200)] for i in range(3010)]
for i in range(1, A + 1):
	for j in range(i, B + 1):
		total[j] += 1
		cnt[j][i ^ j] += 1
for i in range(1, 3001):
	total[i] += total[i - 1]
	for j in range(4101):
		cnt[i][j] += cnt[i - 1][j]
res = 0
for i in range(1, C + 1):
	for j in range(i, D + 1):
		res += total[i] - cnt[i][i ^ j]
print(res)


import sys
(A, B, C, D) = input().strip().split(' ')
[A, B, C, D] = sorted([int(A), int(B), int(C), int(D)])
tuples = {}
vals = {}
for c in reversed(range(1, C + 1)):
	r = range(c, D + 1)
	tuples[c] = len(r)
	if c != C:
		tuples[c] += tuples[c + 1]
	for d in r:
		temp = c ^ d
		if temp not in vals:
			vals[temp] = [1 if i <= c else 0 for i in range(0, C + 1)]
		elif c != C:
			vals[temp][c] = vals[temp][c + 1] + 1
	for t in vals.keys():
		vals[t][c - 1] = vals[t][c]
counter = 0
for a in range(1, A + 1):
	for b in range(a, B + 1):
		temp = a ^ b
		inc = tuples[b]
		penalty = 0
		if temp in vals:
			penalty = vals[temp][b]
		counter += inc - penalty
print(counter)


import os
import sys

def isTupleMore(t1, t2):
	return t1[0] > t2[0] or (t1[0] == t2[0] and t1[1] > t2[1])

def bruteForceCount(numbers):
	result = 0
	total = 0
	for i in range(1, numbers[0] + 1):
		for j in range(1, min(numbers[1], i) + 1):
			for k in range(1, min(numbers[2], j) + 1):
				for l in range(1, min(numbers[3], k) + 1):
					total += 1
					if i ^ j ^ k ^ l != 0:
						result += 1
	print('total:', total)
	return result

def beautifulQuadruples(numbers):
	degree = len(bin(numbers[0])[2:])
	total = 0
	count = [[0 for j in range(numbers[1] + 1)] for i in range(2 ** degree)]
	for i in range(1, numbers[0] + 1):
		for j in range(1, min(i, numbers[1]) + 1):
			res = i ^ j
			count[res][j] += 1
			n2 = min(numbers[2], j)
			n3 = min(n2, numbers[3])
			total += n2 * n3 - n3 * (n3 - 1) // 2
	for i in range(2 ** degree):
		for j in range(numbers[1] - 1, -1, -1):
			count[i][j] += count[i][j + 1]
	for i in range(1, numbers[2] + 1):
		for j in range(1, min(i, numbers[3]) + 1):
			total -= count[j ^ i][i]
	return total
abcd = input().split()
numbers = list(map(int, abcd))
numbers.sort(reverse=True)
result = beautifulQuadruples(numbers)
print(result)


import sys
(A, B, C, D) = input().strip().split()
(A, B, C, D) = sorted([int(A), int(B), int(C), int(D)])
total = [0] * 3010
cnt = [[0 for j in range(4200)] for i in range(3010)]
for i in range(1, A + 1):
	for j in range(i, B + 1):
		total[j] += 1
		cnt[j][i ^ j] += 1
for i in range(1, 3001):
	total[i] += total[i - 1]
	for j in range(4101):
		cnt[i][j] += cnt[i - 1][j]
res = 0
for i in range(1, C + 1):
	for j in range(i, D + 1):
		res += total[i] - cnt[i][i ^ j]
print(res)


import math

def create():
	global cache
	B_Max = 2 ** (int(math.log2(B)) + 1)
	cache = [(B + 1) * [0] for _ in range(B_Max)]
	for i in range(B_Max):
		temp = 0
		for j in range(B, C + 1):
			if j <= j ^ i <= D:
				temp += D - j
			else:
				temp += D - j + 1
		cache[i][-1] = temp
	for i in range(B_Max):
		for j in range(B - 1, 0, -1):
			if j <= i ^ j <= D:
				cache[i][j] = cache[i][j + 1] + (D - j)
			else:
				cache[i][j] = cache[i][j + 1] + (D - j + 1)

def bq(A, B, C, D):
	res = 0
	for i in range(1, A + 1):
		for j in range(i, B + 1):
			res += cache[i ^ j][j]
	return res
(A, B, C, D) = sorted(map(int, input().strip().split()))
create()
print(bq(A, B, C, D))


import bisect
(A, B, C, D) = sorted(map(int, input().split()))
r = {}
for i in range(1, A + 1):
	for j in range(i, B + 1):
		a = i ^ j
		if a not in r:
			r[a] = []
		r[a].append(j)
for k in r:
	r[k].sort()
numZero = 0
for i in range(1, C + 1):
	for j in range(i, D + 1):
		a = i ^ j
		if a in r:
			numZero += bisect.bisect_right(r[a], i)

def count2(i, B, C, D):
	return sum(((C - j + 1) * (2 * (D + 1) - j - C) // 2 for j in range(i, B + 1)))

def count(A, B, C, D):
	return sum((count2(i, B, C, D) for i in range(1, A + 1)))
print(count(A, B, C, D) - numZero)


import sys
nums = input().strip().split(' ')
nums = [int(x) for x in nums]
nums.sort()
nt = [0] * 10000
sum = 0
for i in range(1, nums[2] + 1):
	for j in range(i, nums[3] + 1):
		nt[i ^ j] += 1
		sum += 1
ans = 0
for i in range(1, nums[1] + 1):
	for j in range(1, min(nums[0], i) + 1):
		ans += sum - nt[i ^ j]
	for j in range(i, nums[3] + 1):
		nt[i ^ j] -= 1
		sum -= 1
print(ans)


from math import ceil, log2
(A, B, C, D) = sorted(map(int, input().split()))
X = Y = 0
L = [0] * 2 ** ceil(log2(D + 1))
for i in range(1, C + 1):
	for j in range(i, D + 1):
		L[i ^ j] += 1
		X += 1
for i in range(1, B + 1):
	for j in range(1, min(A, i) + 1):
		Y += X - L[i ^ j]
	for l in range(i, D + 1):
		L[i ^ l] -= 1
		X -= 1
print(Y)


import sys
(A, B, C, D) = input().strip().split()
(A, B, C, D) = sorted([int(A), int(B), int(C), int(D)])
total = [0] * 3010
cnt = [[0 for j in range(4200)] for i in range(3010)]
for i in range(1, A + 1):
	for j in range(i, B + 1):
		total[j] += 1
		cnt[j][i ^ j] += 1
for i in range(1, 3001):
	total[i] += total[i - 1]
	for j in range(4101):
		cnt[i][j] += cnt[i - 1][j]
res = 0
for i in range(1, C + 1):
	for j in range(i, D + 1):
		res += total[i] - cnt[i][i ^ j]
print(res)


def beautifulQuadruples(a, b, c, d):
	(a, b, c, d) = sorted(map(int, [a, b, c, d]))
	total = [0] * 3010
	cnt = [[0 for j in range(4200)] for i in range(3010)]
	for i in range(1, a + 1):
		for j in range(i, b + 1):
			total[j] += 1
			cnt[j][i ^ j] += 1
	for i in range(1, 3001):
		total[i] += total[i - 1]
		for j in range(4101):
			cnt[i][j] += cnt[i - 1][j]
	res = 0
	for i in range(1, c + 1):
		for j in range(i, d + 1):
			res += total[i] - cnt[i][i ^ j]
	print(res)
abcd = input().split()
a = int(abcd[0])
b = int(abcd[1])
c = int(abcd[2])
d = int(abcd[3])
beautifulQuadruples(a, b, c, d)


import sys
(A, B, C, D) = input().strip().split()
(A, B, C, D) = sorted([int(A), int(B), int(C), int(D)])
total = [0] * 3010
cnt = [[0 for j in range(4200)] for i in range(3010)]
for i in range(1, A + 1):
	for j in range(i, B + 1):
		total[j] += 1
		cnt[j][i ^ j] += 1
for i in range(1, 3001):
	total[i] += total[i - 1]
	for j in range(4101):
		cnt[i][j] += cnt[i - 1][j]
res = 0
for i in range(1, C + 1):
	for j in range(i, D + 1):
		res += total[i] - cnt[i][i ^ j]
print(res)


import sys
(A, B, C, D) = input().strip().split()
(A, B, C, D) = sorted([int(A), int(B), int(C), int(D)])
total = [0] * 3010
cnt = [[0 for j in range(4200)] for i in range(3010)]
for i in range(1, A + 1):
	for j in range(i, B + 1):
		total[j] += 1
		cnt[j][i ^ j] += 1
for i in range(1, 3001):
	total[i] += total[i - 1]
	for j in range(4101):
		cnt[i][j] += cnt[i - 1][j]
res = 0
for i in range(1, C + 1):
	for j in range(i, D + 1):
		res += total[i] - cnt[i][i ^ j]
print(res)


def beautifulQuadruples(a, b, c, d):
	(a, b, c, d) = sorted([a, b, c, d])
	max_num = 2 ** len('{:b}'.format(d))
	cnt = [0] * max_num
	all_cnt = 0
	for i in range(1, c + 1):
		for j in range(i, d + 1):
			cnt[i ^ j] += 1
			all_cnt += 1
	ret = 0
	for i in range(1, b + 1):
		for j in range(1, min(a + 1, i + 1)):
			ret += all_cnt - cnt[i ^ j]
		for k in range(i, d + 1):
			cnt[i ^ k] -= 1
			all_cnt -= 1
	return ret
(a, b, c, d) = [int(x) for x in input().split()]
print(beautifulQuadruples(a, b, c, d))


import sys
(A, B, C, D) = input().strip().split(' ')
temp = [int(A), int(B), int(C), int(D)]
temp.sort()
(A, B, C, D) = temp
tot = [0] * 4100
tree = [([0] * 3100).copy() for i in range(4100)]
cnt = [([0] * 3100).copy() for i in range(4100)]

def updateBIT(treeNo, ind):
	while ind < 3100:
		tree[treeNo][ind] += 1
		ind += ind & -ind

def getBITVal(treeNo, ind):
	ret = 0
	while ind > 0:
		ret += tree[treeNo][ind]
		ind -= ind & -ind
	return ret
zero = 0
tot = [0] * 3100
for i in range(1, A + 1):
	for j in range(i, B + 1):
		cnt[i ^ j][j] += 1
		tot[j] += 1
for i in range(len(cnt)):
	for j in range(1, len(cnt[i])):
		cnt[i][j] += cnt[i][j - 1]
for i in range(1, len(tot)):
	tot[i] += tot[i - 1]
ans = 0
for i in range(1, C + 1):
	ans += tot[i] * (D + 1 - i)
	for j in range(i, D + 1):
		zero += cnt[i ^ j][i]
ans -= zero
print(ans)


def parseInput(f):
	return [f(x) for x in input().split()]
limit = 2 ** 12

def calculate(left, right):
	answer = 0
	left_index = 0
	right_index = 0
	left_length = len(left)
	right_length = len(right)
	while left_index < left_length and right_index < right_length:
		if left[left_index] <= right[right_index]:
			answer += right_length - right_index
			left_index += 1
		else:
			right_index += 1
	return answer
left = [[] for i in range(limit)]
right = [[] for i in range(limit)]
(a, b, c, d) = sorted(parseInput(int))
left_count = 0
for i in range(1, b + 1):
	for j in range(1, min(a + 1, i + 1)):
		left[i ^ j].append(i)
for i in range(1, c + 1):
	for j in range(i, d + 1):
		right[i ^ j].append(i)
equalToZero = 0
for i in range(limit):
	equalToZero += calculate(left[i], right[i])
left = []
right = []
for i in range(1, b + 1):
	for j in range(1, min(a + 1, i + 1)):
		left.append(i)
for i in range(1, c + 1):
	for j in range(i, d + 1):
		right.append(i)
total = calculate(left, right)
print(total - equalToZero)


from collections import defaultdict
from bisect import bisect_left
l = [int(x) for x in input().split()]
l.sort()
[a, b, c, d] = l
cs1 = ((w ^ x, x) for w in range(1, a + 1) for x in range(w, b + 1))
cs2 = defaultdict(list)
for y in range(1, c + 1):
	for z in range(y, d + 1):
		cs2[y ^ z].append(y)
for (k, v) in cs2.items():
	v.sort()
cnt = 0
for (r1, x) in cs1:
	ar = cs2[r1]
	p = bisect_left(ar, x)
	cnt += len(ar) - p
tot = 0
for w in range(1, a + 1):
	for x in range(w, b + 1):
		tot += (c - x + 1) * (d - x + 1 + (d - c + 1)) // 2
print(tot - cnt)