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: competition

Starter code:

Solutions:

import sys
#sys.stdin=open("data.txt")
input=sys.stdin.readline

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

a1=0

layers=1
while layers*2<=n: layers*=2

# abacaba pattern
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(i,n&layer)

print(a1)


3

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 = list(map(int, input().split()))
print(solve(n, l, 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 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) 


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

    # print('score({}) = {}'.format(save, ans))
    return ans

def solve(n, r, half_size):
    # count the number of 1s strictly less than r (0 indexed)
    # print(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:
        # r <= half_size
        ans += solve(n // 2, r, half_size // 2)

    return ans

def main():
    n, l, r = list(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)
    print(right - left)

main()


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))


n, l, r = list(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))



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
#do these because l and r are 1 indexed for some reason

b = n
c = []
#brute force cos im suck ass
while b > 1:
    c.append(b%2)
    b = math.floor(b/2)
c.append(1)

if (n == 0):
    print(0)
    return

d = 0
#d is life
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
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)
            


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)


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)

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()

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)

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
#    print(x, n, ret)
    return ret

n, l, r = list(map(int, input().split()))
f(n)
print(dfs(n, r) - dfs(n, l-1))


#!/usr/bin/env python3
# 768B_code.py - Codeforces.com/problemset/problem/768/B by Sergey 2017

import unittest
import sys

###############################################################################
# Code Class (Main Program)
###############################################################################


class Code:
    """ Code representation """

    def __init__(self, test_inputs=None):
        """ Default constructor """

        it = iter(test_inputs.split("\n")) if test_inputs else None

        def uinput():
            return next(it) if it else sys.stdin.readline().rstrip()

        # Reading single elements
        [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):
        """ Main calcualtion function of the class """

        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)

###############################################################################
# Unit Tests
###############################################################################


class unitTests(unittest.TestCase):

    def test_single_test(self):
        """ Code class testing """

        # Constructor test
        test = "7 2 5"
        d = Code(test)
        self.assertEqual(d.n, 7)
        self.assertEqual(d.l, 2)
        self.assertEqual(d.r, 5)

        # Sample test
        self.assertEqual(Code(test).calculate(), "4")

        # Binlist (big endian) test
        self.assertEqual(d.bitlist(6), [1, 1, 0])
        self.assertEqual(d.bitlist(6)[0], 1)

        # Period test
        self.assertEqual(d.period(0), 2)
        self.assertEqual(d.period(2), 8)

        # Start test
        self.assertEqual(d.start(0), 0)
        self.assertEqual(d.start(3), 7)

        # Count test
        self.assertEqual(d.count(6, 8, 3, 5), 0)
        self.assertEqual(d.count(6, 8, 5, 14), 2)

        # Sample test
        test = "10 3 10"
        self.assertEqual(Code(test).calculate(), "5")

        test = "20000000 0 0"
        self.assertEqual(Code(test).calculate(), "0")

        # Sample test
        test = ""
        # self.assertEqual(Code(test).calculate(), "0")

        # My tests
        test = ""
        # self.assertEqual(Code(test).calculate(), "0")

        # Time limit test
        # self.time_limit_test(5000)

    def time_limit_test(self, nmax):
        """ Timelimit testing """
        import random
        import timeit

        # Random inputs
        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"

        # Run the test
        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():

    # Avoiding recursion limitaions
    sys.setrecursionlimit(100000)

    if sys.argv[-1] == "-ut":
        unittest.main(argv=[" "])

    # Print the result string
    sys.stdout.write(Code().calculate())

__starting_point()

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 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:
        # [l, m-1] + [m+1, r] + [m]
        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:
        # [l, r]
        total = ones(n // 2, m, l, r)
    elif m < l < r:
        # [l, r]
        total = ones(n // 2, m, l - m - 1, r - m - 1)
    elif l == m < r:
        # [m+1, r] + m
        total = ones(n // 2, m, 0, r - m - 1) + (1 if n % 2 == 1 else 0)
    elif l < m == r:
        # [l, m] + m
        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()

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)


from functools import lru_cache

n, a, b = map(int, input().split())
a -= 1
b -= 1

if n == 0:
    print(0)
    return

@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)

    #print("n={}, l={}, r={} => {}".format(n, l, r, res))
    return res

print(query(n, a, b))

#!/usr/bin/env python3
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):
#    print(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)

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:  ##   [0-l_count) V [l, r)0
            res += process_rec(n[:-1], l, min(r, l_count))
        if l <= l_count and r > l_count:  ## [l_count, l_count + 1) V [l, r)
            res += m_count
        if r > l_count + 1:  ## [l_count + 1, ...) V [l, r)
            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)


def __starting_point():
    print_output(process(*read_input()))

__starting_point()

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))

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)) 


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 n == 0:
        return 0
    if i == 0:
        return 0

    mx = 2**(n.bit_length())

    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)

def __starting_point():
    solve()
__starting_point()