Harryxun/stf_run huggingface dataset:
a = int(input())
b = int(input())
c = int(input())
print(int(((a+b)*c)/2)

### FIXED CODE ###

a = int(input())
b = int(input())
c = int(input())
print(int(((a+b)*c)/2))
n = print()
a = list(map(int, input().sprit()))
print(reversed(a))

### FIXED CODE ###

n = int(input())
array = list(input().split())
array.reverse()
 
for i in range(n - 1):
    print(array[i] + " ", end = "")

print (array[n - 1])
N = int(input())
x = N
y = N
ansx = N
ansy = N
n = int(N**0.5)
for i in range(x+1):
    if i+1 > n:
        break
    for j in range(y+1):
        if j+1 > x+1:
            break
        if i*j == N:
            if ansx + ansy >i+j:
                ansx,ansy = i,j

print(ansx + ansy -2)

### FIXED CODE ###

N = int(input())
x = N
y = N
ansx = N
ansy = N
ans = []
n = int(N**0.5)
if N**0.5 == int(N**0.5):
    print(int(N**0.5)*2-2)
else:
    for i in range(n+1):
        if N%(i+1) == 0:
            ans.append(i+1)
    ans.append(N)
    if(ans[1]==N):
        print(N-1)
    else:
        for i in range(len(ans)):
            if ansx+ansy>ans[i] + int(N//ans[i]):
                ansx = ans[i]
                ansy =int(N//ans[i])
        print(ansx + ansy -2)
import sys

n = int( raw_input( ) )
eles = []
lines = sys.stdin.readlines()
for line in lines:
	op = line.split( " " )
	op[1] = op[1].strip( )
	if "insert" == op[0]:
		eles.insert( 0, op[1] )
	elif "delete" == op[0]:
		if op[1].rstrip( ) in eles:
			eles.remove( op[1] )
	elif "deleteFirst" == op[0] :
		del eles[0]
	elif "deleteLast" == op[0]:
		eles.pop( )

print( " ".join( eles ) )

### FIXED CODE ###

import sys
from collections import deque

n = int( sys.stdin.readline( ) )
que = deque( )
lines = sys.stdin.readlines()
for line in lines:
	op = line.rstrip().split( " " )
	if "insert" == op[0]:
		que.appendleft( op[1] )
	elif "delete" == op[0]:
		if op[1] in que:
			que.remove( op[1] )
	elif "deleteFirst" == op[0] :
		que.popleft( )
	elif "deleteLast" == op[0]:
		que.pop( )


print( " ".join( que ) )
n = int(raw_input())
nd = len(str(n))

a3 = [357, 375, 537, 573, 735, 753]
arr_a = [[]for i in range(nd-2)]
arr_a[0] = a3
all_num = [357, 375, 537, 573, 735, 753]
for i in range(1, nd-2):
    for j in arr_a[i-1]:
        arr_a[i].append(j*10+3)
        arr_a[i].append(j*10+5)
        arr_a[i].append(j*10+7)
    for k in arr_a[i]:
        all_num.append(k)
# print arr_a

def only_2kind(a,b,n):
    if n <= 3:
        return []
    else:
        all_num = []
        o = [10 * a + b, 10 * b + a, 10 * a + a, 10 * b + b]
        for j in range(n-3):
            o2 = []
            for i in range(len(o)):
                o2.append(o[i]*10+a)
                o2.append(o[i] * 10 + b)
            # print o2
            for i in range(len(o2)):
                if o2[i] != int(str(a)*(j+3)) and o2[i] != int(str(b) * (j + 3)):
                    all_num.append(o2[i]*10+(15-a-b))
            o = o2
        return all_num

all_num+=(only_2kind(3,5,nd)+only_2kind(5,7,nd)+only_2kind(3,7,nd))
all_num.append(n)
all_num.sort()
# print len(all_num)
# for i in all_num:
#     print i
print all_num.index(n)

### FIXED CODE ###

n = int(raw_input().split()[0])

o1 = [3,5,7]
arr = [n]
ans = 0
def check(num):
    l = len(str(num))
    s = []
    for i in range(l):
        if str(num)[i] not in s:
            s.append(str(num)[i])
    if len(s) == 3:
        return True
    else:
        return False

for i in range(8):
    o2 = []
    for num in o1:
        new1 = num*10+3
        new2 = num*10+5
        new3 = num*10+7
        o2.append(new1)
        o2.append(new2)
        o2.append(new3)
        if check(new1):
            arr.append(new1)
            if n == new1:
                ans += 1
        if check(new2):
            arr.append(new2)
            if n == new2:
                ans += 1
        if check(new3):
            arr.append(new3)
            if n == new3:
                ans += 1
    o1 = o2
arr.sort()
print arr.index(n) + ans
s=input()
t=input()
print(s+t)

### FIXED CODE ###

s,t=input().split()
print(t+s)
from math import factorial

N = int(input())
S = [input() for _ in range(N)]

li = []
for s in S:
    st = "".join(sorted(list(s)))
    li.append(st)

di = {}
for i in sorted(li):
    if i in di:
        di[i] = di[i] + 1
    else:
        di[i] = 1


ans = 0
for k, v in di.items():
    if v > 1:
        ans += int(factorial(v) / factorial(2) / factorial(v - 2))

print(ans)



### FIXED CODE ###

N = int(input())
S = [input() for _ in range(N)]

t = {}
ans = 0
for s in S:
    st = "".join(sorted(list(s)))
    if st in t.keys():
        t[st] += 1
        ans += t[st]
    else:
        t[st] = 0

print(ans)
from random import randint


class RollingHash:
    def __init__(self, s):
        self.base = [7073, 7577, 5445, 2742, 6972, 7547, 2267, 286, 6396, 7147,
                     3307, 188, 266, 8253, 2818, 9527, 5110, 1207, 4633, 6196,
                     309, 2646, 7533, 85, 9870, 4730, 6862, 9213, 7456, 7098,
                     6805, 674, 5821, 4864, 8061, 1826, 2219, 459, 5937, 5667,
                     9033, 5552, 7263, 2402, 9809, 3701, 7048, 2874, 8350, 6006,
                     973, 3317, 2522, 5546, 1669, 1545, 7972, 4979, 9905, 173,
                     6812, 7715, 5006, 6068, 6340, 4989, 5510, 6380, 1200, 6739,
                     5527, 4000, 6519, 3448, 2933, 6048, 3133, 1667, 9086, 8368,
                     4914, 7142, 2770, 7752, 391, 7052, 5476, 3105, 8322, 3501,
                     7454, 3167, 8730, 9002, 4564, 138, 2197, 7238, 3411, 7433][randint(0, 100)]
        self.mod = 4611686018427387903
        self.size = len(s)
        self.string = s

        self.hash = self.make_hashtable(s)
        self.pow = self.make_powtable()

    def make_hashtable(self, _s):
        hashtable = [0] * (self.size + 1)
        for i in range(self.size):
            hashtable[i + 1] = (hashtable[i] * self.base + ord(_s[i])) % self.mod
        return hashtable

    def make_powtable(self):
        power = [1] * (self.size + 1)
        for i in range(self.size):
            power[i + 1] = (self.base * power[i]) % self.mod
        return power

    def get_hash(self, left, right):
        """get hash of s[left:right]"""
        return (self.hash[right] - self.hash[left] * self.pow[right - left]) % self.mod

    def contain(self, a):
        """return a in s"""
        m = len(a)
        if m > self.size:
            return False
        hashs = self.get_hash(0, m)
        hasha = 0
        for i in range(m):
            hasha = (hasha * self.base + ord(a[i])) % self.mod
        for i in range(self.size - m + 1):
            if hasha == hashs:
                return True
            hashs = self.get_hash(i, m + i)
        return hasha == hashs


from collections import defaultdict
# d = defaultdict(int)で0で初期化
# d = defaultdict(lambda: 100)で100で初期化
n, s = int(input()), input()
rh = RollingHash(s)


def check(m):
    d = defaultdict(lambda: 10000000)
    for i in range(n - m + 1):
        h = rh.get_hash(i, i + m)
        d[h] = min(d[h], i)
        # m以上離れていて2回目
        if i - d[h] >= m:
            return True
    return False


l, r = 0, n // 2 + 1
while l + 1 < r:
    mid = (l + r) // 2
    if check(mid):
        l = mid
    else:
        r = mid
print(l)


### FIXED CODE ###

n, s = int(input()), input()
dp = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
    for j in range(i + 1, n):
        if s[i] == s[j]:
            dp[i + 1][j + 1] = min(dp[i][j] + 1, j - i)
from itertools import chain
print(max(i for i in chain.from_iterable(dp)))
N=int(input())
A=list(map(int,input().split()))
S=sum(A)
B=[0]*N
B[0]=S-2*sum(A[1::2])
for i in range(n-1):
    B[i+1]=2*A[i]-B[i]
print(*B)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
S=sum(A)
B=[0]*N
B[0]=S-2*sum(A[1::2])
for i in range(N-1):
    B[i+1]=2*A[i]-B[i]

print(*B)
from itertools import accumulate
import math
import fractions

N = int(input())
A = [int(i) for i in input().split()]

#最大公約数で累積和作る
B = [0] * N
R = [0] * N
for i in range(N):
    B[i+1] = (fractions.gcd(B[i],A[i]))
    #逆向き,とったやつの反対端用   
    R[N-i -1] = (fractions.gcd(R[N-i], A[N-i -1]))
 
ans = 0
for i in range(N):
    ans = max(ans, fractions.gcd(B[i], R[i+1]))
print(ans)

### FIXED CODE ###

from itertools import accumulate
import math
import fractions

N = int(input())
A = [int(i) for i in input().split()]

#最大公約数で累積和作る
B = [0] * (N+1)
R = [0] * (N+1)
for i in range(N):
    B[i+1] = (fractions.gcd(B[i],A[i]))
    #逆向き,とったやつの反対端用   
    R[N-i -1] = (fractions.gcd(R[N-i], A[N-1 -i]))
 
ans = 0
for i in range(N):
    ans = max(ans, fractions.gcd(B[i], R[i+1]))
print(ans)
M,N = map(eval,input().split())
user = list(eval(input().replace(" ",",")))
sum = 0
for i in user:
    sum = sum + i
result = M - sum
if result < 0:
    print("-1")
else:
    print(result)

### FIXED CODE ###

N,M = (input()).split()
task = input().split()
list1 = []
sum = 0
for i in task:
    list1.append(i)
for j in list1:
    sum = sum + int(j)
result = int(N) - sum
if result < 0:
    print(-1)
else:
    print(result)
MOD = 1000000007

N = input()
n_list = list(map(int,input().split()))

print(n_list)

result = 0

for i in range(n):
    for j in range(n-i-1)
        result += n_list[i] * n_list[j+1] % MOD
        result = result % MOD

print(result)


### FIXED CODE ###


N = int(input())
n_list = list(map(int,input().split()))

result = 0

s = sum(n_list)
m = 10**9+7

for num in n_list:
    s -= num
    result += num * s % m
    result %= m

print(result)
a,b=map(int,input().split())
s=list(map(int,input().split()))
if a<=sum(s):
    print ("Yes")
else:
    print("No")



### FIXED CODE ###

a,b=map(int,input().split())
count=0
while a>0:
    count+=1
    a-=b
print(count)
n = int(input())

points = []

for i in range(n) :
    point = list(map(int, input(" ")))
    points.append(point)

z = []
w = []

for i in range(len(points)) :
    z.append(points[i][0] + points[i][1])

for i in range(len(points)) :
    w.append(points[i][0] - points[i][1])

max_z = max(z) - min(z)
max_w = max(w) - min(w)

if max_z > max_w :
    print(max_z)
else :
    print(max_w)

### FIXED CODE ###

n = int(input())

points = []

for i in range(n) :
    point = list(map(int, input().split(" ")))
    points.append(point)

z = []
w = []

for i in range(len(points)) :
    z.append(points[i][0] + points[i][1])

for i in range(len(points)) :
    w.append(points[i][0] - points[i][1])

max_z = max(z) - min(z)
max_w = max(w) - min(w)

if max_z > max_w :
    print(max_z)
else :
    print(max_w)
n = int(inut())
x = [input() for i in range(n)]

ans = 1
for i in x:
  ans*i
  
print(ans)

### FIXED CODE ###

n=int(input())
x=list(map(int, input().split()))
 
ans=1
if 0 in x:
  ans=0
else:
  for i in x:
    ans=ans*i
    if ans>10**18:
      ans=-1
      break
print(ans)
n=int(input())
for i in range(n):
    a,b=list(map(int,input().split()))
for i in range(n-2):
    if a[i]==b[i] and a[i+1]==b[i+1] and a[i+2]==b[i+2]:
        print('Yes')
        exit()
print('No')

### FIXED CODE ###

n=int(input())
k=0
l=0
for i in range(n):
    a,b=map(int,input().split())
    if a==b:
        k += 1
        if k==3:
            print('Yes')
            exit()
    else:
        k = 0
print('No')
A = input()
B = input()
A = int(A)
B = int(B)

if A+B == 3:
    ans = 3
elif A+B == 4:
    ans == 2
elif A+B == 5:
    ans == 1
print(ans)

### FIXED CODE ###

A = input()
B = input()
A = int(A)
B = int(B)

if A+B == 3:
    ans = 3
elif A+B == 4:
    ans = 2
elif A+B == 5:
    ans = 1
print(ans)
a,b = map(int,input())
print((b-a)*(b-a+1)//2-b)

### FIXED CODE ###

a,b = map(int,input().split())
print((b-a)*(b-a+1)//2-b)
import collections

import math

n = int(input())
balls = [tuple(map(int, input().split())) for _ in range(n)]


def katamuki(balla, ballb):
    xa, ya = balla
    xb, yb = ballb
    x, y = (xa - xb), (ya - yb)
    dist = math.sqrt(y ** 2 + x ** 2)
    if x == 0:
        return math.inf, dist
    if y == 0:
        return 0.0, dist
    if y / x == -1.0:
        return 1.0, dist
    return y / x, dist


a = []
for i in range(0, n - 1):
    for j in range(i + 1, n):
        a.append(katamuki(balls[i], balls[j]))

counts = collections.Counter(a)
print(n - max(counts.values()))


### FIXED CODE ###

import collections


def calc(balla, ballb):
    xa, ya = balla
    xb, yb = ballb
    return xa - xb, ya - yb


n = int(input())
balls = [tuple(map(int, input().split())) for _ in range(n)]

if n == 1:
    print(1)
    exit()

a = []
for i in range(0, n - 1):
    for j in range(i + 1, n):
        tmp = calc(balls[i], balls[j])
        a += [tmp, tuple(-i for i in tmp)]
counts = collections.Counter(a)

print(n - max(counts.values()))
A, B, C, X = [int(input()) for i in range(4)]
count = 0
if 500*a + 100*b + 50*c == X for a in range(A+1) for b in range(B+1) for c in range(C+1):
  count += 1
print(count)

### FIXED CODE ###

A = int(input())
B = int(input())
C = int(input())
X = int(input())
print(sum(500*a+100*b+50*c==X for a in range(A+1) for b in range(B+1) for c in range(C+1)))
a, b, k = list(map(int, input().split()))
la = []
lb = []
for i in range(1, a+1):
    if a % i == 0:
        la.append(i)
        lsas = sorted(set(la), key=la.index)
        for j in lsas:
            if b % j == 0:
                lb.append(j)

lsbs = sorted(set(lb), key=lb.index))
print(lsbs[len(lsbs)-k])


### FIXED CODE ###

a, b, k = list(map(int, input().split()))
la = []
lb = []
for i in range(1, a+1):
    if a % i == 0:
        la.append(i)
        sa = set(la)
        lsa = list(sa)
        lsas = sorted(lsa)
        for j in lsas:
            if b % j == 0:
                lb.append(j)
s = set(lb)
lsb = list(s)
lsbs = sorted(lsb)
print(lsbs[len(lsbs)-k])
def slove():
    import sys
    input = sys.stdin.readline
    n, k = list(map(int, input().rstrip('\n').split()))
    ab = [ist(map(int, input().rstrip('\n').split()))]
    ab.sort()
    t = 0
    mt = 0
    for a, b in ab:
        t += b
        if t >= k:
            print(a)
            exit()


if __name__ == '__main__':
    slove()


### FIXED CODE ###

n, k = map(int, input().split())
ab = [list(map(int, input().split()))for _ in range(n)]
ab.sort()
cnt = 0
for a, b in ab:
    cnt += b
    if cnt >= k:
        print(a)
        exit()
R,G,B,N = map(int,input().split())
cnt = 0
for r in range((N // R) + 1):
    for g in range((N // G) + 1):
        V = N - (r * R + g * G)
        if V >= o and V % B == 0
            cnt += 1
print(cnt)


### FIXED CODE ###

R,G,B,N = map(int,input().split())
cnt = 0
for r in range((N // R) + 1):
    for g in range((N - (r * R)) // G + 1):
        V = N - (r * R + g * G)
        if V >= 0 and V % B == 0:
            cnt += 1
print(cnt)
for okashi_number in range(k):
	di = int(input())
	D = map(int,input().split())
	for x in range(di)
		A[[x]-1] = 1

for i in range(N):
	if A[i] == 0:
	print(A[i])


### FIXED CODE ###


N,k = map(int,input().split())

A = [0] * N
#print(A)
#print(type(A))

for okashi_number in range(k):
	di = int(input())
	D = list(map(int,input().split()))
	for x in range(di):
		A[D[x]-1]= 1
#print(A)
count = 0
for i in range(N):
	if A[i] == 0:
		count = count + 1
print(count)
(a, b) = [int(x) for x in input().split(' ')]

di = a // b
m = a % b
df = a / b

print('{0} {1} {2:.8f}'.di, m, df))

### FIXED CODE ###

(a, b) = [int(x) for x in input().split()]

di = a // b
m = a % b
df = a / b

print('{0} {1} {2:.8f}'.format(di, m, df))
n=str(input())
f=0
for i in range(len(n)):
  f+=n[i]
if n%f==0:
  print('Yes')
else:
  print('No')
  

### FIXED CODE ###

n=int(input())
f=sum(list(map(int,str(n))))
if n%f==0:
  print('Yes')
else:
  print('No')
a=map(input().split(), int)
r = next(a)
r += next(a)
r -= next(a)
r -= next(a)
print('Left' if r > 0 else 'Balanced' if r == 0 else 'Right')

### FIXED CODE ###

a=map(int,input().split())
r = next(a)
r += next(a)
r -= next(a)
r -= next(a)
print('Left' if r > 0 else 'Balanced' if r == 0 else 'Right')
import numpy as np
n = int(input())
l = np.array(list(map(int, input().split())))
b = 1
def multi(n,b,l):
    for i in range(n):
        b = b * l[i] 
    if b > 10 ** 18:
        b = -1
    b = int(b)
    return b
b = multi(b,l)
print(b)

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

def input():
    return sys.stdin.readline()[:-1]
n = int(input())
l = list(map(int, input().split(" ")))
output = 1

if 0 in l:
    print(0)
    sys.exit()

for i in range(n):
    output = output * int(l[i])
    if output > 10 ** 18:
        output = -1
        break
print(output)
numbers = raw_input().split(' ')

n = numbers[0]
a = numbers[1]
b = numbers[2]

def even_diff(A, B):
  return (B - A) / 2


def odd_diff(N, A, B):
  a_diff = A - 1
  b_diff = N - B
  
  if a_diff > b_diff:
    return N - A
  else:
    return B - 1

if (a - b) % 2 == 0:
  result = even_diff(a, b)
else:
  result = odd_diff(n, a, b)    
  
print(result)

### FIXED CODE ###

import numpy as np

def min_steps_v2(n, a, b):
    n = np.int64(n)
    a = np.int64(a)
    b = np.int64(b)

    if (b - a) % 2 == 0:
        return np.int64(int(b - a) // 2)
 
    # odd case
    a_diff = a - 1
    b_diff = n - b
 
    if a_diff > b_diff:
      steps_to_even = n - b + 1
      remain_steps = min_steps_v2(n, a + (n - b) + 1, n)
    else:
      steps_to_even = a
      remain_steps = min_steps_v2(n, 1, b - a)
 
    return steps_to_even + remain_steps

numbers = input().split(' ')
 
n = int(numbers[0])
a = int(numbers[1])
b = int(numbers[2])
 
print(min_steps_v2(n, a, b))
import math
import numpy as np
def get_prime(n):
    if n<= 1:
        return[]
    prime = [2]
    limit = int(math.sqrt(n))
    
    data = [i + 1 for i in range(2,n,2)]
    while limit > data[0]:
        prime.append(data[0])
        data = [j for j in data if j % data[0] != 0]
    return prime + data
def is_prime(n):
    if n == 1: return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True
n = int(input())
a = get_prime(10**5+1)
b = np.array([0]*(10**5+2))
c =0
d = 0
add = 0
for i in range(1,len(a)):
    if is_prime((a[i]+1)/2):
        d = a[i] 
        b[c:d] = add 
        c = d
        add +=1
b[c:] = add 
b[0::2] = 0

for i in range(n):
    l, r =map(int,input().split())
    print(b[max(0, l[i] - 2)] - b[r[i]])
    

### FIXED CODE ###

q = int(input())
l, r = [0] * q, [0] * q
for i in range(q):
    l[i], r[i] = map(int, input().split())
 
mini = min(min(l), min(r))
maxi = max(max(l), max(r))
ans = [0] * (maxi + 1)
prime = [0] * (maxi + 1)
def judge_prime(n):
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    
    return True if n != 1 else False
 
for i in range((mini + 1) // 2, maxi + 1):
    prime[i] = judge_prime(i)
 
for i in range(mini, maxi + 1, 2):
    ans[i] = ans[i - 2] + 1 if prime[i] and prime[(i + 1) // 2] else ans[i - 2]
for i in range(q):
    print(ans[r[i]] - ans[max(0, l[i] - 2)])
s = str(input())
L = len(s)
dict = {}
for i in range(L+1):
  amari = int(s[i:]) % 2019
  if not(amari in dict.keys()):
    dict[amari] = 1
  else:
    dict[amari] += 1
ans = 0
for key in dict.keys():
  ans += (dict[key]*(dict[key]-1))/2
print(int(ans))

### FIXED CODE ###

s = str(input())
L = len(s)
dict = [0] * 2019
dict[0] += 1
num = 0
for i in range(L-1, (-1), (-1)):
    num += (int(s[i]) * pow(10,(L-i-1), 2019))%2019
    amari = num % 2019
    dict[amari] += 1
ans = 0
for j in range(2019):
    ans += (dict[j]*(dict[j]-1))/2
print(int(ans))
import math
a, b = map(float, input().split()
print(math.floor(a*(b*100)/100))

### FIXED CODE ###

a, b = input().split()
a = int(a)
b = int(b.replace('.', ''))
print(a*b//100)
n=int(input())
arr=[]
arr=list(map(int,input().split()))
mul=1
for i in range(n):
  mul*=arr[i]
  if(mul>1000000000000000000):
    print("-1")
    return
print(mul)


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
a.sort()
ans=1
for i in a:
    ans*=i
    if ans>10**18:
        ans=-1
        break
print(ans)
from collections import deque
from bisect import bisect_right
from copy import deepcopy
n=int(input())
a=list(map(int,input().split()))
edge=[[] for _ in range(n)]
for _ in range(n-1):
    u,v=map(int,input().split())
    u-=1
    v-=1
    edge[u].append(v)
    edge[v].append(u)
visited=[True]*n
lis=[[] for _ in range(n)]
def dfs():
    stack=deque([0])
    visited[0]=False
    lis[0]=[a[0]]
    while stack:
        x=stack.pop()
        for nx in edge[x]:
            if visited[nx]:
                if a[nx]>lis[x][-1]:
                    lis[nx]=lis[x]+[a[nx]]
                else:
                    idx=bisect_right(lis[x],a[nx])
                    cur=deepcopy(lis[x])
                    cur[idx]=a[nx]
                    lis[nx]=cur
                visited[nx]=False
                stack.append(nx)
    return
dfs()
for i in range(n):
    print(len(lis[i]))

### FIXED CODE ###

from collections import deque
from bisect import bisect_left
import sys
sys.setrecursionlimit(10**7)
n=int(input())
a=list(map(int,input().split()))
edge=[[] for _ in range(n)]
for _ in range(n-1):
    u,v=map(int,input().split())
    u-=1
    v-=1
    edge[u].append(v)
    edge[v].append(u)
stack=deque([])
inf=10**18
lis=[inf]*(n+1)
ans=[0 for _ in range(n)]
visited=[True]*n
#print(edge)
def dfs(s):
    visited[s]=False
    idx=bisect_left(lis,a[s])
    stack.append((idx,lis[idx]))
    lis[idx]=a[s]
    ans[s]=bisect_left(lis,inf)
    for x in edge[s]:
        if visited[x]:
            dfs(x)
    idx,val=stack.pop()
    lis[idx]=val
dfs(0)
#print(lis)
for i in range(n):
    print(ans[i])
n, a, b = map(int, input().split())
D = [[0]*2 for _ in range(101010)]
E = [[] for _ in range(n)]


def dfs(cur, pre, d, id):
    D[cur][id] = d
    for nv in E[cur]:
        if nv != pre:
            dfs(nv, cur, d+1, id)


a -= 1
b -= 1
for i in range(n-1):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    E[x].append(y)
    E[y].append(x)
dfs(a, a, 0, 0)
dfs(b, b, 0, 1)
max_d = 0
for i in range(n):
    if D[i][0] < D[i][1]:
        max_d = max(max_d, D[i][1]-1)
print(max_d)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
n, a, b = map(int, input().split())
D = [[0]*2 for _ in range(101010)]
E = [[] for _ in range(n)]


def dfs(cur, pre, d, id):
    D[cur][id] = d
    for nv in E[cur]:
        if nv != pre:
            dfs(nv, cur, d+1, id)


a -= 1
b -= 1
for i in range(n-1):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    E[x].append(y)
    E[y].append(x)
dfs(a, a, 0, 0)
dfs(b, b, 0, 1)
max_d = 0
for i in range(n):
    if D[i][0] < D[i][1]:
        max_d = max(max_d, D[i][1]-1)
print(max_d)
r,g,b = map(int,input().split())
if (10*g + b) % 4 = 0:
  print("YES")
else:
  print("NO")

### FIXED CODE ###

r,g,b = map(int,input().split())
if (10*g + b) % 4 == 0:
  print("YES")
else:
  print("NO")
import bisect
def put(a,b):
 	l=max(len(a),len(b))
    a="0"*l+a
    b="0"*l+a
	s=""
    for i in range(-1,-l-1,-1):
      s+=a[i]+b[i]
    print(s[-1::-1])

def quad(i):
    s=""
    while i>0:
        s+=str(i%4)
        i//=4
    return s[-1::-1]

l=[0,1]
for i in range(1,18):
    l+=[4**i+j for j in l]

n=int(input())
for i in range(len(l)):
    if (n-l[i])%2==0:
        ind=bisect.bisect_left(l,(l[i]-n)//2)
        if l[i]-2*l[ind]==n:
            put(quad(l[i]),quad(l[ind]))
            break


### FIXED CODE ###

def f(n):
    s=""
    while n>0:
        s=str(n%2)+s
        n//=2
        if n==0:
            break
        if n%2==1:
            n+=2
            s="1"+s
        else:
            s="0"+s
        n//=2
    return s

n=int(input())
if n==0:
    print(0)
elif n<0:
    print(f(n*(-2))[:-1])
else:
    print(f(n))
i

### FIXED CODE ###

S=input()
N=len(S)
a=S.count('0')
b=S.count('1')
t=min(a,b)
print(2*t)
n, a, b = map(int, input().split())
ans = 0
for i in range(1, n+1):
  if a<= sum(int(c) for c in str(i)) <= b:
    ams += i
print(ans)

### FIXED CODE ###

n, a, b = map(int, input().split())
ans = 0
for i in range(1, n+1):
  if a<= sum(int(c) for c in str(i)) <= b:
    ans += i
print(ans)
import math
A,B,C,D = map(int,input().split())
n = C * D / math.gcd(C,D)
C_D = (B - A + 1) // n
c = (B - A + 1) // C
d = (B - A + 1) // D
m = int((B - A + 1 ) - (c + d - C_D))
print(m)


### FIXED CODE ###

A, B, C, D = map(int, input().split())
def gcd(a, b):
  if a % b is 0:
    return b
  return gcd(b, a % b)
 
def solve(n):
  return n - (n // C) - (n // D) + (n // (C * D // gcd(C, D)))
 
print(solve(B) - solve(A - 1))