Jon fought bravely to rescue the wildlings who were attacked by the white-walkers at Hardhome. On his arrival, Sam tells him that he wants to go to Oldtown to train at the Citadel to become a maester, so he can return and take the deceased Aemon's place as maester of Castle Black. Jon agrees to Sam's proposal and Sam sets off his journey to the Citadel. However becoming a trainee at the Citadel is not a cakewalk and hence the maesters at the Citadel gave Sam a problem to test his eligibility. 

Initially Sam has a list with a single element n. Then he has to perform certain operations on this list. In each operation Sam must remove any element x, such that x > 1, from the list and insert at the same position $\lfloor \frac{x}{2} \rfloor$, $x \operatorname{mod} 2$, $\lfloor \frac{x}{2} \rfloor$ sequentially. He must continue with these operations until all the elements in the list are either 0 or 1.

Now the masters want the total number of 1s in the range l to r (1-indexed). Sam wants to become a maester but unfortunately he cannot solve this problem. Can you help Sam to pass the eligibility test?


-----Input-----

The first line contains three integers n, l, r (0 ≤ n < 2^50, 0 ≤ r - l ≤ 10^5, r ≥ 1, l ≥ 1) – initial element and the range l to r.

It is guaranteed that r is not greater than the length of the final list.


-----Output-----

Output the total number of 1s in the range l to r in the final sequence.


-----Examples-----
Input
7 2 5

Output
4

Input
10 3 10

Output
5



-----Note-----

Consider first example:

$[ 7 ] \rightarrow [ 3,1,3 ] \rightarrow [ 1,1,1,1,3 ] \rightarrow [ 1,1,1,1,1,1,1 ] \rightarrow [ 1,1,1,1,1,1,1 ]$

Elements on positions from 2-nd to 5-th in list is [1, 1, 1, 1]. The number of ones is 4.

For the second example:

$[ 10 ] \rightarrow [ 1,0,1,1,1,0,1,0,1,0,1,1,1,0,1 ]$

Elements on positions from 3-rd to 10-th in list is [1, 1, 1, 0, 1, 0, 1, 0]. The number of ones is 5.

Difficulty: MEDIUM_HARD
Tags: Divide and conquer

Graph traversal

Constructive algorithms

Starter code:

Solutions:
from math import log2
(n, l, r) = list(map(int, input().split()))
bn = list(map(int, list(bin(n)[2:])))
ans = 0
for i in range(l, r + 1):
	ans += bn[int(log2(i & -i))]
print(ans)


(n, L, R) = list(map(int, input().strip().split()))
if n < 2:
	ans = n % 2
else:
	a = []
	while n != 0:
		a.append(n)
		n = n // 2
	pw2 = []
	pw2.append(1)
	for i in range(1, 51):
		pw2.append(pw2[i - 1] * 2)
	ans = 0
	for i in range(L, R + 1):
		if i % 2 == 1:
			ans += 1
		else:
			cnt = 0
			while i % pw2[cnt] == 0:
				cnt += 1
			ans += a[len(a) - cnt] % 2
print(ans)


import math
(n, l, r) = map(int, input().split())
if n == 0:
	print(0)
	exit(0)
elif n == 1:
	print(1)
	exit(0)
elif n == 2:
	ans = [1, 0, 1]
	print(ans[l - 1:r].count(1))
	exit(0)
elif n == 3:
	ans = [1, 1, 1]
	print(ans[l - 1:r].count(1))
	exit(0)
m = n
if n < 100000:
	a = []
	while n > 1:
		a.append(n % 2)
		n = n // 2
	ans = []
	ans.extend([1, a[-1], 1])
	for i in range(len(a) - 2, -1, -1):
		ans.append(a[i])
		ans.extend(ans[0:-1])
	count = 0
	for i in range(l, r + 1):
		if ans[i - 1] == 1:
			count += 1
	print(count)
	exit()
b = bin(n)[2:]
i = len(b) - 1
d = {}
while n > 1:
	d[2 ** i] = n % 2
	n = n // 2
	i -= 1
count = 0
prev = 2 ** int(math.log(l, 2))
for i in range(l, r + 1):
	if i in d:
		if d[i] == 1:
			count += 1
		prev = i
	else:
		k = i
		j = prev
		while k not in d and k != 1:
			if j < k:
				k = j - (k - j)
			j = j // 2
		if k == 1:
			count += 1
		elif d[k] == 1:
			count += 1
print(count)


from math import *
(n, l, r) = map(int, input().split())
li = []
if n == 0:
	li = [0]
while n > 0:
	li = [n % 2] + li
	n = n // 2
cnt = 0
for i in range(l, r + 1):
	if li[int(log(i & -i, 2))] == 1:
		cnt += 1
print(cnt)


def quantity(x):
	if x < 2:
		return 1
	else:
		return quantity(x // 2) * 2 + 1

def z(x, l, r):
	if x == 0 or l > r:
		return 0
	if x == 1:
		return 1
	k = quantity(x // 2)
	if l <= k + 1 <= r:
		m = x % 2
	else:
		m = 0
	return z(x // 2, l, min(k, r)) + m + z(x // 2, max(1, l - (k + 1)), r - (k + 1))
(x, l, r) = map(int, input().split())
print(z(x, l, r))


def get_size(n):
	res = 1
	while n >= 2:
		res = 2 * res + 1
		n //= 2
	return res

def solve(n, l, r):
	if l > r or n == 0:
		return 0
	if n == 1:
		return 1
	(x, mid) = (get_size(n // 2), 0)
	if l <= x + 1 <= r:
		mid = n % 2
	left_res = solve(n // 2, l, min(r, x))
	right_res = solve(n // 2, max(1, l - x - 1), r - x - 1)
	return mid + left_res + right_res
(n, l, r) = map(int, input().split())
print(solve(n, l, r))


(N, L, R) = map(int, input().split())
S = ''
while N > 0:
	S = str(N % 2) + S
	N //= 2
RAns = 0
for i in range(1, len(S) + 1):
	if R >= 2 ** (i - 1):
		RAns += 1 * int(S[i - 1])
		RAns += (R - 2 ** (i - 1)) // 2 ** i * int(S[i - 1])
L -= 1
LAns = 0
for i in range(1, len(S) + 1):
	if L >= 2 ** (i - 1):
		LAns += 1 * int(S[i - 1])
		LAns += (L - 2 ** (i - 1)) // 2 ** i * int(S[i - 1])
print(RAns - LAns)


def cz(m):
	global ws, n
	if m % 2 == 1:
		return 1
	else:
		s = 2
		i = 1
		while m % (s * 2) == 0:
			s *= 2
			i += 1
		i = ws - i
		if n >> i & 1:
			return 1
		else:
			return 0
import math
(n, l, r) = map(int, input().split())
if n == 0:
	print(0)
else:
	ws = int(math.log2(n))
	print('%d' % sum((cz(i) for i in range(l, r + 1))))


import random, math
from copy import deepcopy as dc

def solution(li, r):
	out = 0
	i = 0
	while r:
		out += (r + 1) // 2 * li[i]
		r = r // 2
		i += 1
	return out

def input_test():
	(n, l, r) = map(int, input().strip().split(' '))
	n = list(map(int, bin(n)[2:]))
	out = solution(n, r)
	out1 = solution(n, l - 1)
	print(out - out1)
input_test()


def f(n):
	if n <= 1:
		return n
	return 2 * f(n // 2) + n % 2

def g(n):
	if n <= 1:
		return 1
	return 2 * g(n // 2) + 1

def solve(n, x):
	global ans
	if x == 0:
		return
	a1 = n // 2
	a2 = n % 2
	if n <= 1:
		if x == 0:
			return
		else:
			ans = n
			return
	c = g(a1)
	if x < c:
		solve(a1, x)
		return
	if x == c:
		ans += f(a1)
		return
	ans += f(a1)
	x -= g(a1)
	if x == 1:
		ans += a2
		return
	ans += a2
	x -= 1
	if x == c:
		ans += f(a1)
		return
	solve(a1, x)
(n, l, r) = map(int, input().split())
ans = 0
solve(n, l - 1)
l = ans
ans = 0
solve(n, r)
r = ans
print(r - l)


import sys
(n, l, r) = map(int, input().split())
l -= 1
r -= 1

def cnt(n):
	if n <= 1:
		return 1
	return 2 * cnt(n // 2) + 1

def rec(n, s, e):
	if s > e:
		return 0
	if s > r or e < l:
		return 0
	if n <= 1:
		return n
	mid = (s + e) // 2
	plus = 0
	if l <= mid <= r:
		plus = n % 2
	return rec(n // 2, s, mid - 1) + rec(n // 2, mid + 1, e) + plus
length = cnt(n)
print(rec(n, 0, length - 1))


from functools import lru_cache

@lru_cache(maxsize=None)
def length(n):
	if n <= 1:
		return 1
	return 2 * length(n // 2) + 1

@lru_cache(maxsize=None)
def solve(n, l, r):
	if l > r:
		return 0
	if n <= 1:
		assert l == r and l == 1
		return n
	mid = length(n // 2) + 1
	if r < mid:
		return solve(n // 2, l, r)
	elif l > mid:
		return solve(n // 2, l - mid, r - mid)
	else:
		return n % 2 + solve(n // 2, l, mid - 1) + solve(n // 2, 1, r - mid)
(n, l, r) = map(int, input().split())
print(solve(n, l, r))


from collections import defaultdict

def ri():
	return map(int, input().split())
pt = defaultdict()
ln = defaultdict()
(n, l, r) = ri()

def lenn(n):
	if n in ln:
		return ln[n]
	if n == 1:
		ln[1] = 1
		return 1
	elif n == 0:
		ln[0] = 1
		return 1
	i = 2 * lenn(n // 2) + 1
	ln[n] = i
	return i

def pn(n):
	if n in pt:
		return pt[n]
	pt[n] = 1 + lenn(n) // 2
	return pt[n]

def findval(i, p, n):
	if p == i:
		return n % 2
	if p > i:
		return findval(i, p - pn(n // 2), n // 2)
	else:
		return findval(i, p + pn(n // 2), n // 2)
ans = 0
p = pn(n)
for i in range(l, r + 1):
	ans += findval(i, p, n)
print(ans)


from sys import stdin
from collections import deque

def ii():
	return int(stdin.readline())

def fi():
	return float(stdin.readline())

def mi():
	return map(int, stdin.readline().split())

def fmi():
	return map(float, stdin.readline().split())

def li():
	return list(mi())

def lsi():
	x = list(stdin.readline())
	x.pop()
	return x

def si():
	return stdin.readline()
a = []
(n, l, r) = mi()
while n > 1:
	a.append(n % 2)
	n //= 2
if n:
	a.append(1)
a.reverse()
(i, s, j) = (2, 0, 0)
while j < len(a):
	if a[j]:
		x = l // i * i + i // 2
		if x < l:
			x += i
		y = r // i * i + i // 2
		if y <= r:
			y += i
		s += (y - x) // i
	i += i
	j += 1
print(s)


from functools import lru_cache
(n, a, b) = map(int, input().split())
a -= 1
b -= 1
if n == 0:
	print(0)
	exit()

@lru_cache(maxsize=None)
def cnt(n):
	if n == 1:
		return 1
	return 2 * cnt(n >> 1) + 1
z = cnt(n)

@lru_cache(maxsize=None)
def query(n, l, r):
	if n == 0:
		return 0
	if n == 1:
		return 1
	if r < cnt(n >> 1):
		return query(n >> 1, l, r)
	if l > cnt(n >> 1):
		return query(n >> 1, l - cnt(n >> 1) - 1, r - cnt(n >> 1) - 1)
	res = n & 1
	if l < cnt(n >> 1):
		res += query(n >> 1, l, cnt(n >> 1) - 1)
	if r > cnt(n >> 1):
		res += query(n >> 1, 0, r - cnt(n >> 1) - 1)
	return res
print(query(n, a, b))


import sys
A = list(map(int, input().split()))
n = A[0]
n1 = n
l = A[1]
r = A[2]
L = []
X = []
if n == 0:
	print(0)
	return
while n > 0:
	L.append(n % 2)
	n = n // 2
near = 1
ans = 0
for i in range(l, r + 1):
	b = -1
	k = i
	d = 1
	f = 0
	while k % d == 0:
		d *= 2
		f += 1
	d /= 2
	f -= 1
	if L[len(L) - f - 1] == 1:
		ans += 1
print(ans)


class A:

	def __init__(self):
		self.count = 0
		self.sz = 0

	def find_binary_rep(self, num):
		if num > 0:
			(k, r) = divmod(num, 2)
			self.sz += 1
			self.find_binary_rep(k)

	def count_ones(self, num, l, r, i, j):
		if l > j or r < i:
			return
		elif l <= i <= r and l <= j <= r:
			self.count += num
		elif num > 1:
			k = num // 2
			m = (i + j - 1) // 2
			self.count_ones(k, l, r, i, m)
			if l <= m + 1 <= r:
				self.count += num % 2
			self.count_ones(k, l, r, m + 2, j)
(n, left, right) = tuple(map(int, input().split()))
a = A()
a.find_binary_rep(n)
total_sz = 2 ** a.sz - 1
a.count_ones(n, left, right, 1, total_sz)
print(a.count)


from sys import stdin, stdout
(n, l, r) = map(int, stdin.readline().split())
d = {}

def value(n):
	if n <= 1:
		return min(n, 1)
	else:
		return value(n // 2) * 2 + n % 2

def numerals(n):
	if n <= 1:
		return 1
	else:
		return numerals(n // 2) * 2 + 1

def cnt(l, r, left, right, number):
	m = left + (right - left) // 2
	ans = 0
	if l == left and r == right:
		if not number in d:
			d[number] = value(number)
		return d[number]
	if l < m:
		ans += cnt(l, min(m - 1, r), left, m - 1, number // 2)
	if r >= m >= l:
		ans += number % 2
	if r > m:
		ans += cnt(max(m + 1, l), r, m + 1, right, number // 2)
	return ans
stdout.write(str(cnt(l, r, 1, numerals(n), n)))


def bit_length(x):
	ans = 0
	while x:
		ans += 1
		x = x // 2
	return max(ans, 1)

def solve(x, pos, size, l, r):
	if x <= 1:
		return x
	ans = 0
	if l < pos:
		ans += solve(x // 2, pos - size, size // 2, l, r)
	if pos >= l and pos <= r:
		ans += x % 2
	if r > pos:
		ans += solve(x // 2, pos + size, size // 2, l, r)
	return ans
(n, l, r) = map(int, input().split())
length = bit_length(n)
x = 1 << length - 1
ans = solve(n, x, x // 2, l, r)
print(ans)


def get_ans(k):
	global mod
	if k == 1:
		ans[0] = 1
	elif k > 0:
		if k == 2:
			mod = 0
		get_ans(k // 2)
		ans.append(2 * ans[-1] + k % 2)
		steps.append(2 * steps[-1] + 1)
		mods.append(k % 2)

def get(k):
	global mod
	if k == 0 or k == -1:
		return 0
	if k == 1:
		return 1
	if k == 2:
		return 1 + mod
	else:
		l = 0
		r = len(steps)
		while r > l + 1:
			m = (r + l) // 2
			if steps[m] > k:
				r = m
			else:
				l = m
		if k == steps[l]:
			return ans[l]
		else:
			return ans[l] + get(k - steps[l] - 1) + mods[l + 1]
(n, l, r) = map(int, input().split())
steps = [1]
mods = [1]
ans = [1]
mod = 1
get_ans(n)
mods.append(0)
if n > 0:
	print(get(r) - get(l - 1))
else:
	print(0)


(n, l, r) = map(int, input().split())
s = ''
a = []
k = n
while k > 1:
	a.append(k % 2)
	k = k // 2
a.append(k)
ans = 0
for i in range(l - 1, r):
	s = '0' + bin(i)[2:]
	cur = 1
	while s[-cur] != '0':
		cur += 1
	ans += a[-cur]
print(ans)


def log2(n):
	i = 0
	a = 1
	while a <= n:
		i += 1
		a *= 2
	return i - 1
import math

def length(n):
	if n == 0 or n == 1:
		return 1
	else:
		m = int(log2(n) + 1)
		return 2 ** m - 1

def solve(n, l, m):
	u = length(n)
	o = math.ceil(u / 2)
	if n == 1:
		return 1
	if n == 0:
		return 0
	(d, t) = divmod(n, 2)
	if m <= o:
		if m == o:
			if l == o:
				return t
			return solve(d, l, o - 1) + t
		return solve(d, l, m)
	elif l >= o:
		if l == o:
			return solve(d, 1, m - o) + t
		return solve(d, l - o, m - o)
	else:
		return solve(d, l, o - 1) + solve(d, 1, m - o) + t
t = 1
while t > 0:
	(n, l, m) = [int(x) for x in input().split()]
	print(solve(n, l, m))
	t -= 1


import sys
LI = lambda : list(map(int, sys.stdin.readline().split()))
MI = lambda : map(int, sys.stdin.readline().split())
SI = lambda : sys.stdin.readline().strip('\n')
II = lambda : int(sys.stdin.readline())
from math import log2

def fun(n, p, l, r):
	m = (l + r) // 2
	if m == p:
		return n % 2
	elif p > m:
		return fun(n // 2, p, m + 1, r)
	else:
		return fun(n // 2, p, l, m - 1)
(n, l, r) = MI()
if n == 0:
	print(0)
	exit()
e = 2 ** (int(log2(n)) + 1) - 1
ans = 0
for i in range(l, r + 1):
	if i % 2:
		ans += 1
	else:
		ans += fun(n, i, 1, e)
print(ans)


(n, l, r) = [int(x) for x in input().strip().split(' ')]

def handlerequest(n, l, r):
	if n == 0 or n == 1:
		return n if l == r else 0
	else:
		size = 2 ** (n.bit_length() - 1) - 1
		if r <= size:
			return handlerequest(n // 2, l, r)
		elif l > size + 1:
			return handlerequest(n // 2, l - size - 1, r - size - 1)
		else:
			return n % 2 + handlerequest(n // 2, l, size) + handlerequest(n // 2, 1, r - size - 1)
print(handlerequest(n, l, r))


dp = {0: 0, 1: 1}

def f(x):
	if x not in dp:
		dp[x] = f(int(x / 2)) * 2 + 1
	return dp[x]
dp2 = {(0, 0): 0}

def dfs(x, n):
	if (x, n) in dp2:
		return dp2[x, n]
	if x == 0 or n == 0:
		return 0
	if dp[x] < n:
		return x
	x2 = int(x / 2)
	fx2 = dp[x2]
	ret = dfs(x2, n)
	if n > fx2:
		ret += dfs(x2, n - fx2 - 1) + x % 2
	dp2[x, n] = ret
	return ret
(n, l, r) = list(map(int, input().split()))
f(n)
print(dfs(n, r) - dfs(n, l - 1))


from math import floor, log

def solve(n, L, R):
	if L > R:
		return 0
	elif n == 1 and L == 1:
		return 1
	elif n == 0:
		return 0
	else:
		mid = 2 ** floor(log(n, 2))
		if mid == n + 1:
			mid /= 2
		return solve(floor(n / 2), L, min(mid - 1, R)) + solve(n % 2, max(1, L - mid + 1), min(1, R - mid + 1)) + solve(floor(n / 2), max(L - mid, 1), R - mid)
(n, l, r) = input().split()
(n, l, r) = (int(n), int(l), int(r))
res = solve(n, l, r)
print(res)


import math
(n, l, r) = [*map(int, input().split())]
binary = [*map(int, list(bin(n)[2:]))]
answer = 0
for i in range(l, r + 1):
	answer += binary[int(math.log2(i & -i))]
print(answer)


from math import log2, trunc

def lo(n):
	i = 0
	while 2 ** i <= n:
		i += 1
	return i

def f(n, l, r):
	if n <= 1:
		return n
	m = 2 ** lo(n) - 1
	if l < m // 2 + 1 and r < m // 2 + 1:
		return f(n // 2, l, r)
	if l > m // 2 + 1 and r > m // 2 + 1:
		return f(n // 2, l - m // 2 - 1, r - m // 2 - 1)
	if l < m // 2 + 1 < r:
		return f(n // 2, l, m // 2) + n % 2 + f(n // 2, 1, r - m // 2 - 1)
	if l == m // 2 + 1 == r:
		return n % 2
	if l == m // 2 + 1:
		return n % 2 + f(n // 2, 1, r - m // 2 - 1)
	if r == m // 2 + 1:
		return n % 2 + f(n // 2, l, m // 2)
(n, l, r) = map(int, input().split())
s = 0
print(f(n, l, r))


import sys
sys.setrecursionlimit(100000)

def score(n):
	factor = 1
	ans = 0
	save = n
	while n > 0:
		ans += factor * (n & 1)
		n >>= 1
		factor *= 2
	return ans

def solve(n, r, half_size):
	if r == 0:
		return 0
	if n < 2:
		return n
	ans = 0
	if r > half_size:
		ans += n & 1
		ans += score(n // 2)
		ans += solve(n // 2, r - half_size - 1, half_size // 2)
	else:
		ans += solve(n // 2, r, half_size // 2)
	return ans

def main():
	(n, l, r) = map(int, input().split())
	b = len(bin(n)) - 2
	half_size = (1 << b - 1) - 1
	right = solve(n, r, half_size)
	left = solve(n, l - 1, half_size)
	print(right - left)
main()


(n, l, r) = map(int, input().split())

class Node(object):

	def __init__(self, n):
		super(Node, self).__init__()
		self.value = n % 2
		self.next = None
		self.mem_size = 1
		if n > 1:
			self.next = Node(n // 2)
			self.mem_size = self.size()

	def size(self):
		if self.next is None:
			return 1
		return 1 + self.next.size() * 2

	def query(self, left, right):
		v = self.value
		next = self.next
		s = 0 if self.next is None else self.next.size()
		rez = 0
		if left <= s < right:
			rez += v
		if self.next is None:
			return rez
		s += 1
		if right == s:
			right -= 1
		if left == s - 1:
			left + 1
		if right < s:
			rez += self.next.query(left, right)
		elif left >= s:
			rez += self.next.query(left - s, right - s)
		else:
			rez += self.next.query(left, s - 1) + self.next.query(0, right - s)
		return rez
node = Node(n)
print(node.query(l - 1, r))


def dels(n):
	c1 = 1
	while n > 1:
		n = n // 2
		c1 = c1 * 2 + 1
	return c1

def recursion(n, l, r):
	if l > r:
		return 0
	if n != 1:
		left_count = dels(n) // 2
		ans = recursion(n // 2, l, min(left_count, r)) + recursion(n // 2, max(left_count + 2, l) - left_count - 1, r - left_count - 1)
		if n % 2 != 0 and left_count + 1 >= l and (left_count + 1 <= r):
			ans += 1
		return ans
	else:
		return 1
(n, l, r) = list(map(int, input().split()))
print(recursion(n, l, r))


from math import *

def kamehameha(pos, target, num):
	if num < 2:
		return num
	if pos + 1 == 2 * target:
		return num % 2
	num //= 2
	pos //= 2
	if target > pos + 1:
		target -= pos + 1
	return kamehameha(pos, target, num)
(n, l, r) = map(int, input().split())
if n == 0:
	print(0)
else:
	ans = 0
	pos = pow(2, floor(log2(n)) + 1) - 1
	for i in range(l, r + 1):
		ans += kamehameha(pos, i, n)
	print(ans)


def main():
	(n, l, r) = list(map(int, input().split()))
	c = n
	h = 0
	while c > 0:
		h += 1
		c //= 2
	c = 2 ** h - 1
	print(ones(n, c, l - 1, r - 1))

def ones(n, c, l, r):
	if n == 1:
		return 1
	if n == 0:
		return 0
	if l == 0 and r == c - 1:
		return n
	m = c // 2
	total = 0
	if l < m < r:
		total = ones(n // 2, m, l, m - 1) + ones(n // 2, m, 0, r - m - 1) + (1 if n % 2 == 1 else 0)
	elif l < r < m:
		total = ones(n // 2, m, l, r)
	elif m < l < r:
		total = ones(n // 2, m, l - m - 1, r - m - 1)
	elif l == m < r:
		total = ones(n // 2, m, 0, r - m - 1) + (1 if n % 2 == 1 else 0)
	elif l < m == r:
		total = ones(n // 2, m, l, m) + (1 if n % 2 == 1 else 0)
	elif l == r < m:
		total = ones(n // 2, m, l, r)
	elif m < l == r:
		total = ones(n // 2, m, l - m - 1, r - m - 1)
	elif l == m == l:
		total = 1 if n % 2 == 1 else 0
	return total

def __starting_point():
	main()
__starting_point()


import math
import sys
a = list(map(int, input().split()))
n = a[0]
l = a[1]
r = a[2]
l = l - 1
r = r - 1
b = n
c = []
while b > 1:
	c.append(b % 2)
	b = math.floor(b / 2)
c.append(1)
if n == 0:
	print(0)
	sys.exit()
d = 0
for x in range(l, r + 1):
	if x % 2 == 0:
		d = d + 1
	else:
		y = x
		p = -1
		while True:
			if y % 2 == 0:
				d = d + c[p]
				break
			else:
				y = (y - 1) / 2
				p = p - 1
print(d)


import sys

def read_input():
	for (idx, line) in enumerate(sys.stdin):
		if idx == 0:
			return (int(x) for x in line.strip().split(' '))

def count_all(n):
	if len(n) == 0:
		return 0
	else:
		return 2 * count_all(n[:-1]) + 1

def count_ones(n):
	if len(n) == 0:
		return 0
	else:
		return 2 * count_ones(n[:-1]) + int(n[-1])

def process_rec(n, l, r):
	if r - l > count_all(n):
		assert False
	if r - l == count_all(n):
		return count_ones(n)
	else:
		l_count = r_count = count_all(n[:-1])
		m_count = int(n[-1])
		res = 0
		if l < l_count:
			res += process_rec(n[:-1], l, min(r, l_count))
		if l <= l_count and r > l_count:
			res += m_count
		if r > l_count + 1:
			res += process_rec(n[:-1], max(l - l_count - 1, 0), r - l_count - 1)
		return res

def process(n, l, r):
	n = '{0:b}'.format(n)
	return process_rec(n, l - 1, r)

def print_output(res):
	print(res)
print_output(process(*read_input()))


def lb_n_dp(x):
	if not x:
		global dp
		dp = [0] * 100
		return 0
	ans = lb_n_dp(x // 2) + 1
	dp[ans] = dp[ans - 1] * 2 + (x & 1)
	return ans

def calc_ans(n, l, r, logn):
	if l == 1 and r == (1 << logn) - 1:
		global dp
		return dp[logn]
	if not logn:
		return n
	logn -= 1
	ln = 1 << logn
	ans = 0
	if l < ln:
		ans += calc_ans(n // 2, l, min(ln - 1, r), logn)
	if l <= ln <= r:
		ans += n & 1
	if ln < r:
		ans += calc_ans(n // 2, max(1, l - ln), r - ln, logn)
	return ans
(n, l, r) = map(int, input().split())
print(calc_ans(n, l, r, lb_n_dp(n)))


from math import ceil, floor
(n, left, right) = map(int, input().split())

def solve(n):
	if n == 0:
		return 0
	a = []
	level = 1
	while n // 2:
		if n % 2 == 0:
			a.append(level)
		n //= 2
		level += 1
	zeroSum = 0
	for l in a[::-1]:
		firstK = ceil((left - 2 ** (level - l)) / 2 ** (level - l + 1))
		lastK = (right - 2 ** (level - l)) // 2 ** (level - l + 1)
		zeroSum += lastK - firstK + 1
	return right - left + 1 - zeroSum
print(solve(n))


import math
(n, l, r) = map(int, input().split())
ls = list(map(int, list(bin(n)[2:])))
rs = 0
for i in range(l, r + 1):
	rs += ls[int(math.log2(i & -i))]
print(rs)


import math
(n, l, r) = [int(e) for e in input().split()]
mylist = [n]
curl = 1
curr = 2 ** math.ceil(math.log(max(n, 1) + 1, 2)) - 1
while curl < l:
	x = mylist[0]
	if x > 1:
		mylist = mylist[1:]
		mylist = [x // 2, x % 2, x // 2] + mylist
	while curl + 2 ** math.ceil(math.log(max(mylist[0], 1) + 1, 2)) - 1 <= l:
		curl += 2 ** math.ceil(math.log(max(mylist[0], 1) + 1, 2)) - 1
		mylist = mylist[1:]
while curr > r:
	x = mylist[-1]
	if x > 1:
		mylist = mylist[:-1]
		mylist += [x // 2, x % 2, x // 2]
	while curr - 2 ** math.ceil(math.log(max(mylist[-1], 1) + 1, 2)) + 1 >= r:
		curr -= 2 ** math.ceil(math.log(max(mylist[-1], 1) + 1, 2)) - 1
		mylist = mylist[:-1]
print(sum(mylist))


from bisect import bisect_left
import sys
import math
input = sys.stdin.readline

def rec(ele):
	if ele <= 1:
		return 1
	g = rec(ele // 2)
	return g + 1 + g

def give(ele, l, r, cl, cr):
	if cr < cl:
		return 0
	if ele <= 1:
		return ele
	mid = (cl + cr) // 2
	a1 = 0
	a2 = 0
	a3 = 0
	if l <= mid and mid <= r:
		a2 = ele % 2
	if mid - 1 >= l:
		a1 = give(ele // 2, l, r, cl, mid - 1)
	if mid + 1 <= r:
		a3 = give(ele // 2, l, r, mid + 1, cr)
	return a1 + a2 + a3
(n, l, r) = map(int, input().split())
limit = rec(n)
print(give(n, l, r, 1, limit))


(n, i0, i1) = list(map(int, input().split()))
i0 -= 1

def len(n):
	l = 1
	if n > 1:
		l += 2 * len(n // 2)
	return l

def get(n, i):
	l = len(n)
	m = l // 2
	a = 0
	if m <= i:
		a += n // 2
		if m < i:
			a += n % 2
		i -= m + 1
	if 0 < i:
		a += get(n // 2, i)
	return a
a = get(n, i1) - get(n, i0)
print(a)


import sys

def debug(x, table):
	for (name, val) in table.items():
		if x is val:
			print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
			return None

def solve():
	(n, l, r) = map(int, input().split())
	ans = f(n, r) - f(n, l - 1)
	print(ans)

def f(n, i):
	if i == 0:
		return 0
	bitlen = len(bin(n)) - 2
	mx = 2 ** bitlen
	if i == mx // 2:
		return n // 2 + n % 2
	elif i < mx // 2:
		return f(n // 2, i)
	else:
		return n // 2 + n % 2 + f(n // 2, i - mx // 2)
solve()


def read(type=1):
	if type:
		file = open('input.dat', 'r')
		line = list(map(int, file.readline().split()))
		file.close()
	else:
		line = list(map(int, input().strip().split()))
	return (line[0], line[1], line[2])

def get_sum(val, x, y, l):
	if val < 2:
		if y > 0:
			return val
		else:
			return 0
	mid = l // 2 + 1
	if x >= mid:
		if x > mid:
			return get_sum(val // 2, x - mid, y - mid, mid - 1)
		else:
			return get_sum(val // 2, x - mid, y - mid, mid - 1) + val % 2
	if y <= mid:
		if y < mid:
			return get_sum(val // 2, x, y, mid - 1)
		else:
			return get_sum(val // 2, x, y, mid - 1) + val % 2
	if x < mid and y > mid:
		return get_sum(val // 2, x, mid - 1, mid - 1) + get_sum(val // 2, 1, y - mid, mid - 1) + val % 2

def solve():
	v = n
	l = 2
	while v > 1:
		v //= 2
		l *= 2
	l -= 1
	return get_sum(n, x, y, l)
(n, x, y) = read(0)
sol = solve()
print(sol)


import math

def solve(n, l, r):
	ans = 0
	lb = list(map(int, bin(n)[2:]))
	for i in range(l, r + 1):
		ans += lb[int(math.log2(i & -i))]
	return ans
(n, l, r) = map(int, input().split(' '))
print(solve(n, l, r))


import sys
sys.setrecursionlimit(10000)

def count_ones(n, limit_left, limit_right):

	def tree_nodes(n):
		if n == 0:
			return 1
		return 2 ** n.bit_length() - 1

	def f(n, start):
		if start > limit_right:
			return 0
		nodes = tree_nodes(n)
		if start + nodes <= limit_left:
			return 0
		if n <= 1:
			return n
		subtree_nodes = (nodes - 1) // 2
		result = f(n // 2, start) + f(n // 2, start + subtree_nodes + 1)
		if limit_left <= start + subtree_nodes <= limit_right:
			result += 1 if n % 2 == 1 else 0
		return result
	return f(n, 0)
(n, left, right) = map(int, sys.stdin.readline().split(' '))
print(count_ones(n, left - 1, right - 1))


import unittest
import sys

class Code:

	def __init__(self, test_inputs=None):
		it = iter(test_inputs.split('\n')) if test_inputs else None

		def uinput():
			return next(it) if it else sys.stdin.readline().rstrip()
		[self.n, self.l, self.r] = list(map(int, uinput().split()))

	def bitlist(self, n):
		result = []
		while n > 0:
			result.append(n & 1)
			n = int(n / 2)
		result.reverse()
		return result

	def period(self, i):
		return 2 << i

	def start(self, i):
		return (1 << i) - 1

	def count(self, s, p, l, r):
		start = 1 if (l - s) % p == 0 else 0
		return (r - s) // p - (l - s) // p + start

	def calculate(self):
		result = 0
		bl = self.bitlist(self.n)
		for (i, n) in enumerate(bl):
			if n == 1:
				period = self.period(i)
				start = self.start(i)
				result += self.count(start, period, self.l - 1, self.r - 1)
		return str(result)

class unitTests(unittest.TestCase):

	def test_single_test(self):
		test = '7 2 5'
		d = Code(test)
		self.assertEqual(d.n, 7)
		self.assertEqual(d.l, 2)
		self.assertEqual(d.r, 5)
		self.assertEqual(Code(test).calculate(), '4')
		self.assertEqual(d.bitlist(6), [1, 1, 0])
		self.assertEqual(d.bitlist(6)[0], 1)
		self.assertEqual(d.period(0), 2)
		self.assertEqual(d.period(2), 8)
		self.assertEqual(d.start(0), 0)
		self.assertEqual(d.start(3), 7)
		self.assertEqual(d.count(6, 8, 3, 5), 0)
		self.assertEqual(d.count(6, 8, 5, 14), 2)
		test = '10 3 10'
		self.assertEqual(Code(test).calculate(), '5')
		test = '20000000 0 0'
		self.assertEqual(Code(test).calculate(), '0')
		test = ''
		test = ''

	def time_limit_test(self, nmax):
		import random
		import timeit
		test = str(nmax) + ' ' + str(nmax) + '\n'
		numnums = [str(i) + ' ' + str(i + 1) for i in range(nmax)]
		test += '\n'.join(numnums) + '\n'
		nums = [random.randint(1, 10000) for i in range(nmax)]
		test += ' '.join(map(str, nums)) + '\n'
		start = timeit.default_timer()
		d = Code(test)
		calc = timeit.default_timer()
		d.calculate()
		stop = timeit.default_timer()
		print('\nTimelimit Test: ' + '{0:.3f}s (init {1:.3f}s calc {2:.3f}s)'.format(stop - start, calc - start, stop - calc))

def __starting_point():
	sys.setrecursionlimit(100000)
	if sys.argv[-1] == '-ut':
		unittest.main(argv=[' '])
	sys.stdout.write(Code().calculate())
__starting_point()


def count(x):
	if x <= 1:
		return 1
	return count(x >> 1) * 2 + 1

def f(n, l, r):
	if l > r:
		return 0
	if n <= 1:
		return n
	cnt = count(n >> 1)
	res = 0
	res += f(n >> 1, l, min(r, cnt))
	if l <= cnt + 1 <= r:
		res += n & 1
	res += f(n >> 1, max(1, l - cnt - 1), r - cnt - 1)
	return res
(n, l, r) = map(int, input().split())
print(f(n, l, r))


(n, L, R) = tuple(map(int, input().split()))
(niveles, k) = ([], 0)
while n > 0:
	k += 1
	niveles.append(n % 2)
	n //= 2
resultado = 0
for i in range(k):
	if niveles[i] == 0:
		continue
	j = 2 ** (k - i)
	(q, r) = divmod(R - L + 1, j)
	resultado += q
	a = L % j
	if a <= j / 2 < a + r or j / 2 <= (a + r) % j < a:
		resultado += 1
print(resultado)


def calc_len(n):
	result = 0
	pow = 0
	while n // 2:
		pow += 1
		n //= 2
	result += 1 << pow + 1
	return result - 1

def calc_1(n, l, r, len):
	if n == 1:
		return 1
	if n == 0:
		return 0
	result = 0
	if l <= len // 2 + 1 and r >= len // 2 + 1 and n % 2:
		result = 1
	if l <= len // 2:
		result += calc_1(n // 2, l, min(r, len // 2), len // 2)
	if r >= len // 2 + 2:
		result += calc_1(n // 2, max(1, l - (len // 2 + 1)), r - (len // 2 + 1), len // 2)
	return result
line = input().split()
n = int(line[0])
l = int(line[1])
r = int(line[2])
len = calc_len(n)
print(calc_1(n, l, r, len))


import sys, math

def func(n, m, q):
	if m == 1:
		return 1
	x = m // 2
	if x + 1 == q:
		return n % 2
	else:
		if q > x + 1:
			q -= x + 1
		return func(n // 2, m // 2, q)

def main():
	(n, l, r) = map(int, sys.stdin.readline().strip().split())
	count = 0
	if n >= 1:
		m = 2 ** (int(math.log(n, 2)) + 1) - 1
		for i in range(l, r + 1):
			if func(n, m, i) == 1:
				count += 1
	sys.stdout.write(str(count) + '\n')
main()


import sys
sys.setrecursionlimit(10000)
(n, l, r) = map(int, input().split())
ntob = []
ntob_len = 0
one_count = [0] * 51

def getNumbOfOne(dest, len):
	mid = pow(2, len - 1)
	if dest < mid:
		if dest == 0:
			return 0
		else:
			return getNumbOfOne(dest, len - 1)
	elif dest == mid:
		return one_count[len - 1] + ntob[len - 1]
	else:
		return one_count[len - 1] + ntob[len - 1] + getNumbOfOne(dest - mid, len - 1)
if n < 2:
	print(n)
else:
	while n != 0:
		ntob.insert(0, n % 2)
		n = n // 2
	ntob_len = len(ntob)
	one_count[1] = 1
	for i in range(2, ntob_len + 1):
		one_count[i] = one_count[i - 1] * 2 + ntob[i - 1]
	print(getNumbOfOne(r, ntob_len) - getNumbOfOne(l - 1, ntob_len))


from os import path
import sys
from functools import cmp_to_key as ctk
from collections import deque, defaultdict as dd
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from itertools import permutations
from datetime import datetime
from math import ceil, sqrt, log, gcd

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

def si():
	return input()

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

def li():
	return list(mi())
abc = 'abcdefghijklmnopqrstuvwxyz'
abd = {'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}
mod = 1000000007
inf = float('inf')
vow = ['a', 'e', 'i', 'o', 'u']
(dx, dy) = ([-1, 1, 0, 0], [0, 0, 1, -1])

def func(a, x):
	ans = 0
	n = len(a)
	for i in range(n, 0, -1):
		x1 = (1 << i) - 1
		if x >= x1:
			ans += a[i - 1]
			x -= x1
			if x > 0:
				ans += a[i] % (2 * a[i - 1])
				x -= 1
	return ans

def solve():
	(n, l, r) = mi()
	a = [n]
	while n > 1:
		a.append(n // 2)
		n //= 2
	a.reverse()
	cnt1 = [a[0]]
	for i in range(1, len(a)):
		cnt1.append(2 * cnt1[i - 1] + a[i] % 2)
	tot = (1 << len(cnt1)) - 1
	if r > tot:
		r -= tot
	if l > tot:
		l -= tot
	x = func(cnt1, r)
	y = func(cnt1, l - 1)
	print(x - y)
solve()


(n, l, r) = map(int, input().split())
l -= 1
r -= 1
op = 0
curn = n
while curn > 1:
	curn //= 2
	op += 1
length = 1
for i in range(op):
	length = 2 * length + 1

def get_ans(n, l, r, curl, curr):
	if l == curl and r == curr:
		return n
	length = curr - curl + 1
	mid = (curr + curl) // 2
	ans = 0
	if l < mid:
		ans += get_ans(n // 2, l, min(mid - 1, r), curl, mid - 1)
	if r > mid:
		ans += get_ans(n // 2, max(l, mid + 1), r, mid + 1, curr)
	if l <= mid and r >= mid:
		ans += n % 2
	return ans
print(get_ans(n, l, r, 0, length - 1))


def midof(n):
	i = 1
	while i <= n:
		i <<= 1
	return i >> 1

def count_one(n, l, r):
	if n < 2:
		return n
	mid = midof(n)
	if l == 0 and r == 2 * mid - 1:
		return n
	if n + 1 == 2 * mid:
		return r - l + 1
	c = n % 2 * (l <= mid <= r)
	if l < mid:
		c += count_one(n // 2, l, r if r < mid else mid - 1)
	if r > mid:
		c += count_one(n // 2, l - mid if l > mid else 1, r - mid)
	return c
print(count_one(*map(int, input().split())))


def ffs(x):
	return (x & -x).bit_length() - 1
(n, l, r) = [int(x) for x in input().split()]
top_number = 0
ones = 0
if n == 0:
	print(ones)
	quit()
else:
	for i in range(51):
		top_number = 2 ** i
		if top_number > n:
			break
	values = []
	divided = n
	while divided != 1.0:
		values.append(divided)
		divided = divided // 2
	values.append(1)
	mods = [values[-1 * (i + 1)] % 2 for i in range(len(values))]
	for i in range(l, r + 1):
		index = ffs(i)
		ones += mods[index]
print(ones)


import sys

def debug(x, table):
	for (name, val) in table.items():
		if x is val:
			print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
			return None

def solve():
	(n, l, r) = map(int, input().split())
	bit_len = len(bin(n)[2:])
	cnt = 0
	for i in range(l, r + 1):
		off = bit_len - 1
		for j in range(bit_len - 1):
			if i & 1 << j:
				break
			else:
				off -= 1
		cnt += n >> off & 1
	print(cnt)

def __starting_point():
	solve()
__starting_point()


from math import log, ceil
(n, f, l) = [int(i) for i in input().split()]
try:
	a = 2 ** ceil(log(n, 2)) - 1
except Exception:
	pass

def fun(n, ind, depth):
	if n < 2:
		return [n]
	if n == 2:
		return [1, 0, 1]
	else:
		cnt = a // 2 ** depth
		ind += cnt
		p1 = [cnt]
		p2 = [cnt]
		if f < ind:
			p1 = fun(n // 2, ind - cnt, depth + 1)
		if l > ind:
			p2 = fun(n // 2, ind + 1, depth + 1)
		return p1 + [n % 2] + p2
if n == 0:
	print(0)
else:
	a = fun(n, 1, 1)
	cnt = 0
	i = 0
	for j in range(len(a)):
		if a[j] < 2:
			i += 1
		else:
			i += a[j]
		if i > l:
			break
		if a[j] == 1 and i >= f and (i <= l):
			cnt += 1
	print(cnt)


def get(nn, x):
	res = 0
	i = -1
	while x:
		res += (x + 1) // 2 * nn[i]
		x //= 2
		i -= 1
	return res

def toBin(n):
	res = []
	while n:
		res.append(n % 2)
		n //= 2
	if res:
		return res
	else:
		return [0]

def raw(n):
	if n < 2:
		return [n]
	else:
		temp = raw(n // 2)
		return temp + [n % 2] + temp
(n, l, r) = list(map(int, input().split()))
nn = toBin(n)
print(get(nn, r) - get(nn, l - 1))


citire = list(map(int, input().split()))
k = 0

def get_p2(n):
	i = 1
	while n >= i:
		i *= 2
	i -= 1
	return int(i)
p = get_p2(citire[0])
suma = 0

def rez(l, r, len, n):
	global suma
	jumlen = len // 2 + 1
	len = (len + 1) // 2 - 1
	if l < jumlen:
		rez(l, min(jumlen - 1, r), len, n // 2)
	if l <= jumlen and r >= jumlen:
		suma += n % 2
	if r > jumlen:
		rez(max(1, l - jumlen), r - jumlen, len, n // 2)
rez(citire[1], citire[2], p, citire[0])
print(suma)


def seg(n, l, r, lr, rg):
	if rg < l or r < lr or n == 0:
		return 0
	if n == 1:
		return 1
	md = (lr + rg) // 2
	return seg(n // 2, l, r, lr, md - 1) + seg(n % 2, l, r, md, md) + seg(n // 2, l, r, md + 1, rg)
(n, l, r) = map(int, input().split())
tmp = n
cnt = 0
while tmp != 0:
	cnt = cnt * 2 + 1
	tmp //= 2
print(seg(n, l, r, 1, cnt))


(n, l, r) = map(int, input().split())
ar = []
if n == 0:
	print(0)
else:
	while n != 0:
		ar = [n % 2] + ar
		n //= 2
	ans = 0
	for i in range(l, r + 1):
		c = 0
		while i % 2 == 0:
			i //= 2
			c += 1
		if ar[c] == 1:
			ans += 1
	print(ans)


import sys
input = sys.stdin.readline
(n, l, r) = map(int, input().split())
a1 = 0
layers = 1
while layers * 2 <= n:
	layers *= 2
for i in range(l, r + 1):
	layer = layers
	while i % 2 == 0:
		layer //= 2
		i //= 2
	if n // layer % 2 == 1:
		a1 += 1
print(a1)


def main():
	ans = 0

	def length(n):
		if n <= 1:
			return 1
		x = length(n // 2)
		return x + length(n % 2) + x

	def f(n, i, j):
		nonlocal ans, l, r
		if n <= 1:
			if n == 1 and i >= l and (j <= r):
				ans += 1
			return
		mid = (i + j) // 2
		if l <= mid:
			x = f(n // 2, i, mid - 1)
		y = f(n % 2, mid, mid)
		if r >= mid:
			z = f(n // 2, mid + 1, j)
	(n, l, r) = map(int, input().split(' '))
	l -= 1
	r -= 1
	f(n, 0, length(n) - 1)
	return ans
print(main())


a = {0: 0, 1: 1}
x = input().split()
n = int(x[0])
l = int(x[1])
r = int(x[2])

def search(p, left, right):
	mid = left + right >> 1
	if right < l or left > r:
		return 0
	if p in a:
		return a[p]
	if r <= mid:
		return search(p >> 1, left, mid - 1) + (r == mid and p % 2)
	if l >= mid:
		return search(p >> 1, mid + 1, right) + (l == mid and p % 2)
	return search(p >> 1, left, mid) + (l <= mid and mid <= r and p % 2) + search(p >> 1, mid + 1, right)
print(search(n, 1, 2 ** (len(bin(n)) - 2) - 1))


from sys import stdin

def find(n, l, r):
	if l > R or r < L:
		return 0
	if n < 2:
		if l >= L and r <= R:
			return n
		else:
			return 0
	else:
		mid = (l + r) // 2
		return find(n // 2, l, mid - 1) + find(n % 2, mid, mid) + find(n // 2, mid + 1, r)
(N, L, R) = map(int, stdin.readline().split())
length = 1
while length < N:
	length = length * 2 + 1
print(find(N, 1, length))


import math
from queue import *

def norecursivo(n, l, r):
	cola = Queue()
	h = log2(n) + 1
	m = cantnodos(h) if h > 2 else 0
	cola.put((n, m))
	cont = 0
	while not cola.empty():
		(n, pos) = cola.get()
		if pos >= l and pos <= r and (n % 2 == 1):
			cont += 1
		h = log2(n) + 1
		m = cantnodos(h - 1) if h > 2 else 0
		if h > 1:
			if pos > l:
				cola.put((n >> 1, pos - m - 1))
			if pos < r:
				cola.put((n >> 1, pos + m + 1))
	return cont

def log2(n):
	iteraciones = 0
	cociente = n
	while cociente > 0:
		cociente = cociente >> 1
		iteraciones = iteraciones + 1
	return iteraciones

def cantnodos(h):
	return pow(2, h - 2) - 1
(n, l, r) = [int(n) for n in input().split()]
cont = norecursivo(n, l - 1, r - 1)
print(cont)


def getLength(num):
	if num <= 1:
		return 1
	return getLength(int(num / 2)) * 2 + 1

def getOne(num, l, r, L, R):
	if num == 0 or l > R or r < L:
		return 0
	if num == 1:
		return 1
	mid = int(L + getLength(int(num / 2)))
	return getOne(int(num / 2), l, r, L, mid - 1) + getOne(int(num % 2), l, r, mid, mid) + getOne(int(num / 2), l, r, mid + 1, R)
ip = input()
number = ip.split()
num = int(number[0])
l = int(number[1])
r = int(number[2])
length = getLength(num)
res = getOne(num, l, r, 1, length)
print(res)


def mid(ln, rn):
	return (ln + rn) // 2

def rfn(l, r, n, ln, rn):
	if rn < l or r < ln or n == 0:
		return 0
	if n == 1:
		return 1
	mn = mid(ln, rn)
	return rfn(l, r, n // 2, ln, mn - 1) + rfn(l, r, n % 2, mn, mn) + rfn(l, r, n // 2, mn + 1, rn)
(n, l, r) = map(int, input().strip().split())
(N, total) = (n, 0)
while N != 0:
	total = total * 2 + 1
	N //= 2
print(rfn(l, r, n, 1, total))


def find(curLevel, num, inf, sup):
	if inf > sup:
		return 0
	if curLevel == 1:
		return num
	numCur = 2 ** curLevel - 1
	midCur = numCur // 2 + 1
	if inf == sup and inf == midCur:
		return num % 2
	if inf > midCur:
		return find(curLevel - 1, num // 2, inf - midCur, sup - midCur)
	elif inf == midCur:
		return num % 2 + find(curLevel - 1, num // 2, 1, sup - midCur)
	elif sup < midCur:
		return find(curLevel - 1, num // 2, inf, sup)
	elif sup == midCur:
		return num % 2 + find(curLevel - 1, num // 2, inf, sup - 1)
	else:
		return num % 2 + find(curLevel - 1, num // 2, inf, midCur - 1) + find(curLevel - 1, num // 2, 1, sup - midCur)
(u, l, r) = [int(i) for i in input().split()]
cu = u
level = 0
while cu:
	level += 1
	cu //= 2
if r > 2 ** level - 1:
	r = 2 ** level - 1
print(find(level, u, l, r))


def cnt(x):
	if x < 2:
		return 1
	return 2 * cnt(x // 2) + 1

def calc(n, x):
	if x == 0:
		return 0
	if n < 2:
		return n
	m = cnt(n // 2)
	if x <= m:
		return calc(n // 2, x)
	elif x == m + 1:
		return n // 2 + n % 2
	else:
		return n // 2 + n % 2 + calc(n // 2, x - m - 1)
(n, l, r) = map(int, input().split())
print(calc(n, r) - calc(n, l - 1))


import math

def next_power_of_2(x):
	x += 1
	return 1 if x == 0 else 2 ** math.ceil(math.log2(x))

def value(n, l, r):
	if n == 1:
		return 1
	size = next_power_of_2(n) - 1
	next_n = math.floor(n / 2)
	mid = math.floor(size / 2) + 1
	v = 0
	lv = 0
	rv = 0
	if l <= mid and mid <= r:
		v += n % 2
	if l < mid:
		lv = value(next_n, l, min(mid - 1, r))
	if r > mid:
		rv = value(next_n, max(1, l - mid), r - mid)
	v = v + lv + rv
	return v

def create(n):
	if n == 1:
		return [1]
	else:
		return create(math.floor(n / 2)) + [n % 2] + create(math.floor(n / 2))
[n, l, r] = [int(x) for x in input().split()]
print(value(n, l, r))


(n, l, r) = list(map(int, input().split()))
ln = 0
ans = 0
curr = 1
while curr <= n:
	curr *= 2
	ln += 1
ln -= 1
for i in range(l, r + 1):
	if curr > i:
		res = 1
		res2 = 0
		while res & i == 0:
			res *= 2
			res2 += 1
		if res2 <= ln:
			msk = n & 1 << ln - res2
			ans += msk != 0
print(ans)


def cnt(n):
	res = 0
	while n:
		n >>= 1
		res += 1
	return res

def cal(n, i, c):
	if i == 1 << c:
		return n & 1
	elif i < 1 << c:
		return cal(n // 2, i, c - 1)
	else:
		return cal(n // 2, i - (1 << c), c - 1)
(n, l, r) = map(int, input().split())
ans = 0
c = cnt(n)
if n > 0:
	for i in range(l, r + 1):
		if cal(n, i, c - 1):
			ans += 1
print(ans)


def sz(n):
	if n < 2:
		return 1
	return 2 * sz(n // 2) + 1

def f(n, l, r):
	if l > r or n == 0:
		return 0
	if n == 1:
		return 1
	x = sz(n // 2)
	md = 0
	if l <= x + 1 <= r:
		md = n % 2
	return md + f(n // 2, l, min(r, x)) + f(n // 2, max(1, l - (x + 1)), r - (x + 1))
(n, l, r) = map(int, input().split())
print(f(n, l, r))


from sys import stdin
import math

def Log(n):
	for i in range(52):
		num = int(math.pow(2, i))
		if n < num:
			return i - 1

def dfs(n, nl, nr, l, r):
	if l <= nl and r >= nr:
		return n
	mid = (nl + nr) // 2
	num = 0
	if mid >= l and mid <= r:
		num += n % 2
	if l < mid:
		num += dfs(n // 2, nl, mid - 1, l, r)
	if r > mid:
		num += dfs(n // 2, mid + 1, nr, l, r)
	return num
(n, l, r) = map(int, stdin.buffer.readline().split())
if n == 0:
	print(0)
	exit()
num = Log(n)
(nl, nr) = (1, int(math.pow(2, num + 1)) - 1)
ans = dfs(n, nl, nr, l, r)
print(ans)


def get_len(n):
	if n <= 1:
		return 1
	return get_len(n // 2) * 2 + 1

def dvcq(n, ll, rr):
	if ll == rr:
		return 0
	if n <= 1:
		return n
	mid = get_len(n // 2)
	if rr <= mid:
		return dvcq(n // 2, ll, rr)
	elif mid < ll:
		return dvcq(n // 2, ll - (mid + 1), rr - (mid + 1))
	else:
		return (n & 1) + dvcq(n // 2, ll, mid) + dvcq(n // 2, 0, rr - (mid + 1))
(N, L, R) = map(int, input().split())
print(dvcq(N, L - 1, R))


import sys, math
from io import BytesIO, IOBase
from types import GeneratorType
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def func(n, m, q):
	if m == 1:
		return 1
	x = m // 2
	if x + 1 == q:
		return n % 2
	else:
		if q > x + 1:
			q -= x + 1
		return func(n // 2, m // 2, q)

def main():
	(n, l, r) = map(int, sys.stdin.readline().strip().split())
	count = 0
	if n >= 1:
		m = 2 ** (int(math.log(n, 2)) + 1) - 1
		for i in range(l, r + 1):
			if func(n, m, i) == 1:
				count += 1
	sys.stdout.write(str(count) + '\n')
main()


import sys

def recur(bnry, prefix_sum, idx):
	if bnry[0] == '1':
		prefix_sum[idx] = 2 * prefix_sum[idx - 1] + 1
	elif bnry[0] == '0':
		prefix_sum[idx] = 2 * prefix_sum[idx - 1]
	bnry = bnry[1:]
	if len(bnry):
		recur(bnry, prefix_sum, idx + 1)
	else:
		return 0

def cal(bnry, num, prefix_sum, idx):
	if num == pow(2, idx) - 1:
		if bnry[idx - 1] == '1':
			return prefix_sum[idx - 1] * 2 + 1
		else:
			return prefix_sum[idx - 1] * 2
	elif num == pow(2, idx - 1):
		if bnry[idx - 1] == '1':
			return prefix_sum[idx - 1] + 1
		else:
			return prefix_sum[idx - 1]
	elif num == pow(2, idx - 1) - 1:
		return prefix_sum[idx - 1]
	if num > pow(2, idx - 1):
		if bnry[idx - 1] == '1':
			return prefix_sum[idx - 1] + 1 + cal(bnry, num - pow(2, idx - 1), prefix_sum, idx - 1)
		else:
			return prefix_sum[idx - 1] + cal(bnry, num - pow(2, idx - 1), prefix_sum, idx - 1)
	elif num < pow(2, idx - 1):
		return cal(bnry, num, prefix_sum, idx - 1)
sys.setrecursionlimit(100000)
(n, l, r) = list(map(int, input().split(' ')))
bnry = bin(n)
prefix_sum = [0] * 51
if n == 0:
	print(0)
else:
	recur(bnry[2:], prefix_sum, 1)
	print(cal(bnry[2:], r, prefix_sum, len(bnry[2:])) - cal(bnry[2:], l - 1, prefix_sum, len(bnry[2:])))


def srch(x, prec, prec1, poz, h):
	a = x // 2
	r = x % 2
	if prec < poz <= prec + 2 ** h - 1:
		return srch(x // 2, prec, prec1, poz, h - 1)
	if poz == prec + 2 ** h:
		return prec1 + x // 2 + x % 2
	if prec + 2 ** h < poz <= prec + 2 ** (h + 1) - 1:
		return srch(x // 2, prec + 2 ** h, prec1 + x // 2 + x % 2, poz, h - 1)
s = input()
ls = s.split()
n = int(ls[0])
l = int(ls[1])
r = int(ls[2])
if n == 0:
	print(0)
	quit()
if n == 1:
	print(1)
	quit()
kn = 0
aux = 1
while aux * 2 <= n:
	aux *= 2
	kn += 1
if l == 1:
	lnr = 0
else:
	lnr = srch(n, 0, 0, l - 1, kn)
rnr = srch(n, 0, 0, r, kn)
print(rnr - lnr)


(n, l, r) = list(map(int, input().split()))
tmplen = len(bin(n)[2:])
cnt = 0

def getans(num, left, right):
	global cnt
	if right < l or r < left or right < left:
		return
	mid = (left + right) // 2
	if mid <= r and mid >= l:
		cnt += num % 2
	getans(num // 2, left, mid - 1)
	getans(num // 2, mid + 1, right)
getans(n, 1, 2 ** tmplen - 1)
print(cnt)


import sys
sys.setrecursionlimit(10000)

def count_ones(n, limit_left, limit_right):
	subarray = [None] * (limit_right - limit_left + 1)

	def f(n, start):
		if start > limit_right:
			return
		nodes = max(1, 2 ** n.bit_length() - 1)
		if start + nodes <= limit_left:
			return
		subtree_nodes = (nodes - 1) // 2
		if subtree_nodes > 0:
			f(n // 2, start)
			f(n // 2, start + subtree_nodes + 1)
		if limit_left <= start + subtree_nodes <= limit_right:
			subarray[start - limit_left + subtree_nodes] = n % 2
	f(n, 0)
	return sum(subarray)
(n, left, right) = map(int, sys.stdin.readline().split(' '))
print(count_ones(n, left - 1, right - 1))


(n, l, r) = map(int, input().split())
binl = tuple(map(int, bin(n)[2:]))
res = 0
for i in range(len(binl)):
	if not binl[i]:
		continue
	cur = (1 << i) + ((l >> i + 1) - 1 << i + 1)
	dif = 1 << i + 1
	while cur <= r:
		if cur >= l:
			res += 1
		cur += dif
print(res)


def solve(n, m, r, l, i):
	if r < l or m > i or n == 0:
		return 0
	if n == 1:
		return 1
	mid = (l + i) // 2
	return solve(n // 2, m, r, l, mid - 1) + solve(n % 2, m, r, mid, mid) + solve(n // 2, m, r, mid + 1, i)
l = list(map(int, input().split()))
n = l[0]
m = l[1]
r = l[2]
x = n
i = 1
while x > 1:
	i = i * 2 + 1
	x //= 2
ans = solve(n, m, r, 1, i)
print(ans)


(n, l, r) = map(int, input().split())
ar = []
cnt = 0
if n < 2:
	print(n)
	exit()
while n > 1:
	ar.append(n % 2)
	cnt += 1
	n //= 2
pw = [2 ** i for i in range(cnt - 1, -1, -1)]
ans = 0
pnt = 0
for i in range(l, r + 1):
	if i % 2 == 1:
		ans += 1
		continue
	con = i // 2
	for j in range(cnt):
		if con % pw[j] == 0:
			ans += ar[j]
			break
print(ans)


(n, l, r) = map(int, input().split())
k = n
a = []
if n != 0:
	while k != 0:
		a = [k % 2] + a
		k = k // 2
else:
	a = [0]
count = 0
for i in range(l, r + 1):
	j = 0
	while i % 2 == 0:
		i = i // 2
		j += 1
	if a[j] == 1:
		count += 1
print(count)


def cnt(n):
	if n < 2:
		return 1
	return cnt(n // 2) * 2 + 1

def sum1(n, x):
	if x == 0:
		return 0
	if n < 2:
		return n
	m = cnt(n // 2)
	if x <= m:
		return sum1(n // 2, x)
	if x == m + 1:
		return n // 2 + n % 2
	return n // 2 + n % 2 + sum1(n // 2, x - m - 1)
(n, l, r) = map(int, input().split())
print(sum1(n, r) - sum1(n, l - 1))


import math

def log(n):
	i = 0
	while n > 0:
		i = i + 1
		n = n // 2
	return i

def length(n):
	if n == 0:
		return 1
	a = log(n)
	return 2 ** a - 1

def solve(n, left, right):
	l = length(n)
	middle = (l + 1) // 2
	if n == 1:
		return 1
	if n == 0:
		return 0
	if left > right:
		return 0
	(half, rem) = divmod(n, 2)
	if middle == right and middle == left:
		return rem
	elif middle >= right:
		if middle == right:
			return solve(half, left, middle - 1) + rem
		else:
			return solve(half, left, right)
	elif left >= middle:
		if middle == left:
			return solve(half, 1, right - middle) + rem
		else:
			return solve(half, left - middle, right - middle)
	else:
		return solve(half, left, middle - 1) + solve(half, 1, right - middle) + rem
(a1, a2, a3) = [int(x) for x in input().split()]
print(solve(a1, a2, a3))


import sys
import math
(n, l, r) = map(int, input().split())
if n == 0:
	print(0)
	sys.exit()
log = math.ceil(math.log2(n))
cnt = [-1] * (math.ceil(math.log2(n)) + 2)
cnt[1] = 1
cnt[0] = 1
plus = [0] * (log + 2)
plus[1] = 1
t = 0
cnt1 = 0

def diver(n, i):
	global t, cnt1
	if t > r:
		return
	if cnt[i] != -1 and n > 1:
		if cnt[i] + t < l or cnt[i] > r:
			t += cnt[i]
		elif l <= t and cnt[i] + t <= r:
			t += cnt[i]
			cnt1 += plus[i]
		else:
			diver(n // 2, i - 1)
			diver(n % 2, n % 2)
			diver(n // 2, i - 1)
		return
	if n == 0:
		t += 1
	elif n == 1:
		if t >= l - 1 and t <= r - 1:
			cnt1 += 1
		t += 1
	else:
		diver(n // 2, i - 1)
		diver(n % 2, n % 2)
		diver(n // 2, i - 1)
		cnt[i] = cnt[i - 1] * 2 + cnt[n % 2]
		plus[i] = 2 * plus[i - 1] + plus[n % 2]
diver(n, math.ceil(math.log2(n)))
print(cnt1)


from __future__ import print_function
from collections import *
from sys import stdin
from bisect import *
from heapq import *
from math import *
g = lambda : stdin.readline().strip()
gl = lambda : g().split()
gil = lambda : [int(var) for var in gl()]
gfl = lambda : [float(var) for var in gl()]
gcl = lambda : list(g())
gbs = lambda : [int(var) for var in g()]
rr = lambda x: reversed(range(x))
mod = int(1000000000.0) + 7
inf = float('inf')
(n, l, r) = gil()

def getLength(n):
	if n == 0:
		return 1
	return (1 << int(log2(n)) + 1) - 1

def isOne(n, i):
	while n > 1:
		smallLength = getLength(n // 2)
		if i == smallLength + 1:
			n &= 1
		elif i <= smallLength:
			n //= 2
		else:
			n //= 2
			i -= smallLength + 1
	return n
val = 0
r = min(r, getLength(n))
if l > r:
	print(0)
	exit()
for i in range(l, r + 1):
	val += isOne(n, i)
print(val)