Harryxun/stf_run huggingface dataset:
import heapq
N = int(input())
ab = [tuple(map(int, input().split())) for i in range(N-1)]
c = list(map(int, input().split()))

print(sum(c) - max(c))
c = list(map(lambda x: x*(-1), c))
heapq.heapify(c)
d = [[0, i] for i in range(N)]
g = [set() for i in range(N)]
for a, b in ab:
    d[a-1][0] += 1
    d[b-1][0] += 1
    g[a-1].add(b-1)
    g[b-1].add(a-1)
d.sort(reverse=True, key=lambda x: x[0])
for i in range(N):
    d[i][0] = -1
d[0][0] = -1 * heapq.heappop(c)


def dfs(start):
    for x in g[start]:

        if d[x][0] == -1:

            d[x][0] = d[x][0] * heapq.heappop(c)

            dfs(x)


dfs(0)
d.sort(key=lambda x: x[1])

ans = [""]*N
for i in range(N):
    ans[i] = str(d[i][0])
print(" ".join(ans))


### FIXED CODE ###

import heapq
import sys
sys.setrecursionlimit(20000)
N = int(input())
ab = [tuple(map(int, input().split())) for i in range(N-1)]
c = list(map(int, input().split()))

print(sum(c) - max(c))
c = list(map(lambda x: x*(-1), c))
heapq.heapify(c)
d = [[0, i] for i in range(N)]
g = [set() for i in range(N)]
for a, b in ab:
    d[a-1][0] += 1
    d[b-1][0] += 1
    g[a-1].add(b-1)
    g[b-1].add(a-1)
d.sort(reverse=True, key=lambda x: x[0])
for i in range(N):
    d[i][0] = -1


ans = ["-1"]*N
ans[d[0][1]] = str(-1 * heapq.heappop(c))


def dfs(start):
    for x in g[start]:
        if ans[x] == "-1":
            ans[x] = str(-1 * heapq.heappop(c))
            dfs(x)


dfs(d[0][1])
d.sort(key=lambda x: x[1])


print(" ".join(ans))
s = input()
n = len(s) // 2
lst = [(i + j) for (i, j) in zip(s[::2], s[1::2])]

for i in range(n):
    if lst[i] == 'hi':
        check = 1
    else:
        check = 0
        break

if check == 1:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

s = input()
n = len(s) // 2
lst = [(i + j) for (i, j) in zip(s[::2], s[1::2])]

check = 0
for i in range(n):
    if lst[i] == 'hi':
        check = 1
    else:
        check = 0
        break

if len(s) % 2 == 1:
    check = 0

if check == 1:
    print("Yes")
else:
    print("No")
import sympy

N=int(input())
count=0
for i in range(N):
    if sympy.divisor_count(i+1)==8 and (i+1)%2==1:
        count+=1

print(count)


### FIXED CODE ###

N=int(input())
count=0
if N>=195:
    print(5)
elif N>=189:
    print(4)
elif N>=165:
    print(3)
elif N>=135:
    print(2)
elif N>=105:
    print(1)
else:
    print(0)
# the uppercase letters are encoded as 65 to 90
# I want to put A as 0, so Z is 25

def letter_to_int(letter):
    return ord(letter)-65


def int_to_letter(encoded_value):
    return chr(encoded_value+65)


def shift_string(N, string):
    shifted_string = ""
    for char in string:
        encoding = letter_to_int(char)
        # mod ensures it wraps around, eg N=3 sends Z to C
        shifted = (encoding+N)%26
        decoded_to_letter = int_to_letter(shifted)
        shifted_string = shifted_string + decoded_to_letter
    return shifted_string


if __name__ == "__main__":
    test1 = \
"""2
ABCXYZ"""
    test2 = \
"""0
ABCXYZ"""
    test3 = \
"""13
ABCDEFGHIJKLMNOPQRSTUVWXYZ"""
    various_tests = [test1, test2, test3]
"""    for test in various_tests:
        lines = test.split("\n")
        N = int(lines[0])
        string = lines[1]
        print(shift_string(N, string))"""
    N = int(input())
    string = input()
    print(shift_string(N, string))

### FIXED CODE ###

# the uppercase letters are encoded as 65 to 90
# I want to put A as 0, so Z is 25

def letter_to_int(letter):
    return ord(letter)-65


def int_to_letter(encoded_value):
    return chr(encoded_value+65)


def shift_string(N, string):
    shifted_string = ""
    for char in string:
        encoding = letter_to_int(char)
        # mod ensures it wraps around, eg N=3 sends Z to C
        shifted = (encoding+N)%26
        decoded_to_letter = int_to_letter(shifted)
        shifted_string = shifted_string + decoded_to_letter
    return shifted_string


if __name__ == "__main__":
    test1 = \
"""2
ABCXYZ"""
    test2 = \
"""0
ABCXYZ"""
    test3 = \
"""13
ABCDEFGHIJKLMNOPQRSTUVWXYZ"""
    various_tests = [test1, test2, test3]
    """for test in various_tests:
        lines = test.split("\n")
        N = int(lines[0])
        string = lines[1]
        print(shift_string(N, string))"""
    N = int(input())
    string = input()
    print(shift_string(N, string))
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

s = input()
x, y = MAP()

F = s.split("T")
print(F)
x_list = []
y_list = []
for i, n in enumerate(F):
	if i%2 == 0:  # x軸方向
		x_list.append(len(n))
	else:
		y_list.append(len(n))

"""
x_listから順に取り出して右か左に動く．
dp[i][x] := i回目の移動後にx座標がxとなっていることができるか
y軸も同様
"""

if len(x_list) == 0:
	if x == 0 and y == 0:
		print("Yes")
		sys.exit()
	else:
		print("No")
		sys.exit()

x -= x_list.pop(0)  # 最初のFの分だけ右に動く
x_sum = sum(x_list)
y_sum = sum(y_list)


if (x_sum-x)%2 != 0:  # パリティ
  print("No")
  sys.exit()
else:
  n_x = (x_sum-abs(x))//2
if (y_sum-y)%2 != 0:
  print("No")
  sys.exit()
else:
  n_y = (y_sum-abs(y))//2

dp_x = [[False]*(abs(n_x)+1) for _ in range(len(x_list)+1)]
dp_y = [[False]*(abs(n_y)+1) for _ in range(len(x_list)+1)]
dp_x[0][0] = True
dp_y[0][0] = True

for i in range(1, len(x_list)+1):
	for j in range(n_x+1):
		if dp_x[i-1][j]:
			dp_x[i][j] = True
			if j+x_list[i-1] < n_x+1:
				dp_x[i][j+x_list[i-1]] = True

for i in range(1, len(y_list)+1):
	for j in range(n_y+1):
		if dp_y[i-1][j]:
			dp_y[i][j] = True
			if j+y_list[i-1] < n_y+1:
				dp_y[i][j+y_list[i-1]] = True

if dp_x[-1][-1] and dp_y[-1][-1]:
	print("Yes")
else:
	print("No")


### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

s = input()
x, y = MAP()

x_list = []
y_list = []
for i, s_ in enumerate(s.split('T')):
	if i == 0:
		x -= len(s_)
	elif i % 2 == 0:
		x_list.append(len(s_))
	else:
		y_list.append(len(s_))

def check(d, x):
  se =set([0])
  for dx in d:
    se={a+b for a,b in product(se,[-dx,dx])}  # 直積としてDPを計算
  return (x in se)

print('Yes' if check(x_list, x) and check(y_list, y) else 'No')
n = int(input())
l = [int(input()) for i in range(n)].sort()
print(int(0.5*l[-1] + sum(l[-1])))

### FIXED CODE ###

n = int(input())
l = list()
for i in range(n):
  a = int(input())
  l.append(a)

l.sort()
p = 0.5*l[-1] + sum(l[:-1])
print(int(p))
n=int(input())
lis=list(map(int,input().split()))
num=(n*(n+1))//2
if sum(lis)%num!=0:
  print("NO")
  exit()
ans=0
for k in range(n):
  if -(lis[i]-lis[i-1]-sum(lis)//num)%n!=0:
    print("NO")
    exit()
  ans+=-(lis[i]-lis[i-1]-sum(lis)//num)//n
if ans == sum(lis)//num:print("YES")
else:print("NO")


### FIXED CODE ###

n=int(input())
lis=list(map(int,input().split()))
num=(n*(n+1))//2
ll=sum(lis)
if ll%num!=0:
  print("NO")
  exit()
ans=0
for i in range(n):
  if abs(lis[i]-lis[i-1]-ll//num)%n!=0:
    print("NO")
    exit()
  ans+=abs(lis[i]-lis[i-1]-ll//num)//n
if ans == ll//num:print("YES")
else:print("NO")
import math
n = int(input())
a = list(map(int,input().split()))
ans = a[0]
for x in a:
    ans = math.gcd(x,ans)
print(ans)

### FIXED CODE ###

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b,a%b)
n = int(input())
a = list(map(int,input().split()))
ans = a[0]
for x in a:
    ans = gcd(x,ans)
print(ans)
int(A * B)

### FIXED CODE ###

a, b = (int(x) for x in input().split())
print(a * b)
import numpy as np

#%%
N, M, X = [int(i) for i in input().split()]
CA = [[] for i in range(N)]
for i in range(N):
    k = list(map(int, input().split()))
    CA[i] = k[:]
CA = np.array(CA)
#%%
cnt = (10 ** 5) * N + 1

for i in range(2 ** N):
    score = np.zeros(N + 1)
    for j in range(N):
        if (i >> j) & 1:
            score += CA[j]
    for k in range(1, N + 1):
        if score[k] < X:
            break
    else:
        if score[0] < cnt:
            cnt = score[0]
            
if cnt != (10 ** 5) * N + 1:
    print(int(cnt))
else:
    print(-1)


### FIXED CODE ###

import numpy as np

#%%
N, M, X = [int(i) for i in input().split()]
CA = [[] for i in range(N)]
for i in range(N):
    k = list(map(int, input().split()))
    CA[i] = k[:]
CA = np.array(CA)
#%%
cnt = (10 ** 5) * N + 1

for i in range(2 ** N):
    score = np.zeros(M + 1)
    for j in range(N):
        if (i >> j) & 1:
            score += CA[j]
    for k in range(1, M + 1):
        if score[k] < X:
            break
    else:
        if score[0] < cnt:
            cnt = score[0]
            
if cnt != (10 ** 5) * N + 1:
    print(int(cnt))
else:
    print(-1)
while True:
    n = raw_input()
    if n == 0:break
    sum = 0
    for i in n:
        sum += int(i)
    print sum

### FIXED CODE ###

while True:
    n = str(raw_input())
    if n == "0":break
    sum = 0
    for i in n:
        sum += int(i)
    print sum
from itertools import*
from math import*
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float("inf")
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)
"""
#memo化再帰
memo = [-1]*(110000)
def rec(n):
    if n==0:
        return 0
    if memo[n] != -1:
        return memo[n]
    res = n
    pow6,pow9 = 1,1
    while pow6 <=n:
        res = min(res,rec(n-pow6)+1)
        pow6 *= 6
    while pow9 <= n:
        res = min(res,rec(n-pow9)+1)
        pow9 *= 9
    memo[n] = res
    return memo[n]
N = int(input())
print(rec(N))
"""
"""
#もらうDP
N = int(input())
dp=[inf]*110000
dp[0] = 0
for n in range(1,N+1):
    pow6,pow9 = 1,1
    while pow6<=n:
        dp[n] = min(dp[n],dp[n-pow6]+1)
        pow6 *= 6
    while pow9 <= n:
        dp[n] = min(dp[n],dp[n-pow9]+1)
        pow9 *= 9
print(dp[N])
"""
#配るDP
N = int(input())
dp=[inf]*(110000)
for i in range(110000):
    dp[i] = N 
dp[0]=0
for n in range(N):
    pow6,pow9 = 1,1
    while pow6<=N:
        dp[n+pow6] = min(dp[n+pow6],dp[n]+1)
        pow6 *= 6
    while pow9 <=N:
        dp[n+pow9] = min(dp[n+pow9],dp[n]+1)
        pow9 *= 9
print(dp[N])

### FIXED CODE ###

N = int(input())
l = [1,6,9,36,81,216,729,1296,6561,7776,46656,59049]
dp = [N]*(N+1)
dp[0]=0

for i in range(1,N+1):
    for j in l:
        if i-j >= 0:
            dp[i] = min(dp[i],dp[i-j]+1)
print(dp[N])
h = []
for i in range(N) : 
    s = input()
    h.append(int(s))
    
h = sorted(h)
minDiff = h[len(h) - 1] - h[0]
for i in range(N) : 
    try : 
        diff = h[len(h) - K + i] - h[i]
        print(f"diff={h[len(h) - K + i]} - {h[i]} = {diff}")
        minDiff = min(minDiff , diff)
        
    except : 
        if i == 0 : minDiff = 0
        continue
print(minDiff)

### FIXED CODE ###

s = input().split(" ")
N = int(s[0])
K = int(s[1])

h = []
for i in range(N) : 
    s = input()
    h.append(int(s))
    
h = sorted(h)
minDiff = h[len(h) - 1] - h[0]
for i in range(N) : 
    try : 
        diff = h[i + K - 1] - h[i]
        minDiff = min(minDiff , diff)
        
    except : 
        if i == 0 : minDiff = 0
        continue
print(minDiff)
n = int(input())

G = [g for g in [1, 4, 10, 23, 57, 132, 301, 701] if g < n]
while True:
	g = int(2.25 * G[-1])
	if g > n:
		break
	G.append(g)
G.reverse()

A = [int(input()) for _ in range(n)]
cnt = 0
for g in G:
	for j, v in enumerate(A[g:]):
		while j >= 0 and A[j] > v:
			A[j+g] = A[j]
			j -= g
			cnt += 1
		A[j+g] = v

print(len(G))
print(*G)
print(cnt)
for a in A:
	print(a)


### FIXED CODE ###

import sys

n = int(input())
if n == 1:
	G = [1]
else:
	G = [g for g in [1, 4, 10, 23, 57, 132, 301, 701] if g < n]
	while True:
		g = int(2.25 * G[-1])
		if g > n:
			break
		G.append(g)
	G.reverse()

A = list(map(int, sys.stdin))
cnt = 0
for g in G:
	for j, v in enumerate(A[g:]):
		while j >= 0 and A[j] > v:
			A[j+g] = A[j]
			j -= g
			cnt += 1
		A[j+g] = v

print(len(G))
print(*G)
print(cnt)
for a in A:
	print(a)
A, B, M = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
mina, minb = min(a), min(b)
minv = mina+minb
for _ in range(M):
    x, y, c = [int(i) for i in input().split()]
    x -= 1
    y -= 1
    minv = min(minv, a[x]+a[y]-c)


print(minv)

### FIXED CODE ###

A, B, M = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
mina, minb = min(a), min(b)
minv = mina+minb
for _ in range(M):
    x, y, c = [int(i) for i in input().split()]
    x -= 1
    y -= 1
    minv = min(minv, a[x]+b[y]-c)


print(minv)
N,K = [int(x) for x in input().split()]
S = input()
li = [1]
ans = 0
cnt = 0
for ind,s in enumerate(S[:-1]):
    if(s==S[ind+1]):
        li[-1]+=1
    else:
        li.append(1)
for ind,i in enumerate(li):
    if(ind%2==1 and cnt<=K):

### FIXED CODE ###

N,K = [int(x) for x in input().split()]
S = input()
#%%
li = [1]
ans = 0
cnt = 0

for ind,s in enumerate(S[:-1]):
    if(s==S[ind+1]):
        li[-1]+=1
    else:
        li.append(1)

#%%
for ind,i in enumerate(li):
    if(ind==0):
        ans += i-1
    elif(ind<=2*K):
        ans += i
    else:
        ans += max(i-1,0)
print(ans)
while True:
	x = int(input())
	for i in range(x):
		li = list(input())
		li1 = int("".join(sorted(li)))
		li2 = int("".join(sorted(li,reverse=True)))
		print(li2-li1)


### FIXED CODE ###

ti = int(input())
for i in range(ti):
	x = list(input())
	print(int(''.join(sorted(x,reverse=True))) - int(''.join(sorted(x))))
import collections

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

limit = int(A[-1] ** 0.5)
ans = 0
while limit > A[0]:
    if len(A) == 1:
        ans += 1
    elif A[0] != A[1]:
        ans += 1
    A = [i for i in A if i % A[0] != 0]
    
a = collections.Counter(A)
print(ans + len([i[0] for i in a.items() if i[1] == 1]))

### FIXED CODE ###

from collections import Counter

N = int(input())
A = [int(i) for i in input().split()]
num = set(A)
count = Counter(A)
dp = [True] * (10**6 + 1)

for a in num:
    for n in range(a+a, 10**6+1, a):
        dp[n] = False

ans = 0
for a in num:
    if count[a] == 1 and dp[a] == True:
        ans += 1

print(ans)
N=int(input())
*P,=map(int,input().split())

i=c=0
while i<L:
  if P[i]==i+1:
    c+=1
    i+=1
  i+=1
print(c)

### FIXED CODE ###

N=int(input())
P=map(int,input().split())
S=[]
for x,y in zip(P, range(1,N+1)):
    if x==y: S.append(y)

S.append('$')
L=len(S)

lake=[]
lake.append(S[0])
i=1
a=0
while i<L:
    if S[i]=='$':
     a+=1
    elif lake[0]+1!=S[i]:
     a+=1
     lake=[]
     lake.append(S[i])
    else:
     lake.append(S[i])
    i+=1
print(a)
import math
n = int(input())
a = [int(i) for i in input().split()]

if len(a) == 1:
    print(a[0])
else:
    res = math.gcd(a[0],a[1])
    for i in range(2,n):
        res = math.gcd(res,a[i])
    print(res)

### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]

def func_gcd(a,b):
    if b == 0:
        return a
    else:
        return func_gcd(b,a%b)

if len(a) == 1:
    print(a[0])
else:
    res = func_gcd(a[0],a[1])
    for i in range(2,n):
        res = func_gcd(res,a[i])
    print(res)
import sys

s = list(input())
set_s = set(s)
new_s = list(set_s)
new_s.sort()
for i in range(26):
    if ord(new_s[i]) != 97+i:
        print(chr(97+i))
        sys.exit()
print('None')

### FIXED CODE ###

import sys

s = list(input())
set_s = set(s)
new_s = list(set_s)
new_s.sort()
for i in range(26):
    if ord(new_s[i]) != 97+i:
        print(chr(97+i))
        sys.exit()
    if len(new_s) == i+1:
        if i == 25:
            break
        print(chr(98+i))
        sys.exit()
print('None')
n,q = map(int,input().split())
a=[[] for i in range(n)]
p=[]*n
l=[0]*n

def dfs(parent,current):
    for i in a[current-1]:
        if i != parent:
            l[i-1] += l[current-1]
            dfs(current,i)


for i in range(n-1):
    t1,t2 = map(int,input().split())
    a[t1-1].append(t2)
    a[t2-1].append(t1)
    
for i in range(q):
    t1,t2 = map(int,input().split())
    l[t1-1]+=t2
dfs(-1,1)

print(" ".join(map(str,l)))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

readline = sys.stdin.readline

n,q = map(int,readline().split())
a=[[] for i in range(n)]
l=[0 for _ in range(n)]
ans=[0 for _ in range(n)]

def dfs(parent,current,value):
    value += l[current]
    ans[current] = value
    for i in a[current]:
        if i == parent:
            continue
        dfs(current,i,value)


for i in range(n-1):
    t1,t2 = map(int,readline().split())
    a[t1-1].append(t2-1)
    a[t2-1].append(t1-1)
    
for i in range(q):
    t1,t2 = map(int,readline().split())
    l[t1-1]+=t2
dfs(-1,0,0)

print(" ".join(map(str,ans)))
a, b = map(int, raw_input().split())
d = a/b
r = a%b
f = a*1.0/b
print ???%d %d %f??? % (d,r,f)

### FIXED CODE ###

a, b = map(int, raw_input().split())
d = a/b
r = a%b
f = a*1.0/b
print '%d %d %f' % (d,r,f)
AB,BC,CA=map(int,input()split())
print(AB*BC/2)

### FIXED CODE ###

AB,BC,CA=map(int,input().split())
print(int(AB*BC/2))
import string
def main():
    s = input()
    if s == "zyxwvutsrqponmlkjihgfedcba":
        print(-1)
        return
    for i in "abcdefghijklmnopqrstuvwxyz@":
        if i == "@":
            t = 0
            for x in range(len(s), -1, 0):
                for y in rnage(x-1, -1, -1):
                    if x == y:
                        continue
                    if s[x] > s[y]:
                        print(s.translate(string.maketrans(s[x],x[y])))
                        return 
        if s.count(i) == 0:
            print (s + i)
            break

main()



### FIXED CODE ###

import string

alp = string.ascii_lowercase

def main():
    s = input()
    if len(s) < 26:
        for i in alp:
            if i not in s:
                print (s + i)
                return
    if s == alp[::-1]:
        print(-1)
        return
    L = len(s)
    tmp = []
    tt = ''
    for i, ss in enumerate( s ):
        tmp += [ s[L-i-1] ]
        if s[L-i-1] > s[L-i-2]:
            ans = s[:L-i-2]
            tt = s[L-i-2] 
            break
    tmp.sort()
    for i in tmp:
        if i > tt:
            print (ans + i)
            break
main()
N=int(input())
A=sorted(list(map(int,input().split())))
C=[0]*(max(A)+1)

for i in A:
    C[i]+=1

if len(C)==0:
    print(C[0])
else:
    T=max(C[0]+C[1],C[-1]+C[-2])
    for i in range(1,max(A)):
        T=max(T,C[i-1]+C[i]+C[i+1])
    print(T)

### FIXED CODE ###

N=int(input())
A=sorted(list(map(int,input().split())))
C=[0]*(max(A)+1)

for i in A:
    C[i]+=1

if len(C)==1:
    print(C[0])
else:
    T=max(C[0]+C[1],C[-1]+C[-2])
    for i in range(1,max(A)):
        T=max(T,C[i-1]+C[i]+C[i+1])
    print(T)
word = input().lower()
texts = []
while TRUE:
  str = input()
  if str == 'END_OF_TEXT':
    break
  texts.extend([s.lower() for s in str.split()] )
    

ans = texts.count(word)

print ans

### FIXED CODE ###

word = input().lower()
texts = []
while True:
  str = input()
  if str == 'END_OF_TEXT':
    break
  texts.extend([s.lower() for s in str.split()] )
    

ans = texts.count(word)

print(ans)
n = int(input())
x = [int(input()) for i in range(n)]

ans = 1
for i in x:
  ans = ans*i
  
if ans > 1000000000000000000:
  ans = -1

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=1079
N=int(input())

a=str(N*100/108)
b=str((N+1)*100/108)

if a+1 <=b:
    print(round(a+0.5))
else:
    print(":(")


### FIXED CODE ###

# N=1079
N=int(input())

a=int(N*100/110)-1

flg=False

for i in range (N-a+1):
    if ((a+i)*1.08)//1==N:
        print(a+i)
        exit()
    else:
        pass
print(':(')
# cook your dish here
n,k=list(map(int,input().split()))
if n%k==0:
    print(n%k)
else:
    a=[]
    x=int(n/k)
    for i in range(1,x+1):
        r=n-(i*(k-1))
        a.append(abs(r-i))   
    print(min(a))    
    

### FIXED CODE ###

# cook your dish here
n,k=list(map(int,input().split()))
if n%k==0:
    print(0)
else:
    print(1)
n, a, b = [int(i) for i in input().split()]
if a == 0:
    print(0)
else:
    x = (n // (a + b)) + 1
    balls = []
    for i in range(x):
        balls += list("b" * a) + list("r" * b)
    ans = 0
    for i in range(n):
        if balls[i] == "b":
            ans += 1
    print(ans)


### FIXED CODE ###

n, a, b = [int(i) for i in input().split()]
ans = (n // (a + b)) * a
rem = n % (a + b)
ans += min(rem, a)
print(ans)
N, x = input().split()
N = int(N)
x = int(x)
al = [int(a) for a in input().split()]

al.sort()

used = 0
ans = 0
for a in enumerate(al:
    if used+a > x:
        break
    used += a
    ans += 1

print(ans)
    
        
        


### FIXED CODE ###

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

al.sort()

cum = [sum(al[:i+1])for i in range(len(al))]

ans = N-1
for i in range(len(al)):
    if cum[i] == x:
        ans = i+1
        break
    elif cum[i]>x:
        ans = i
        break
print(ans)
N = int(input())
A = int(input())

ans = N % A

if A == 0:
    print("No")
    exit()
print("Yes" if ans <= A else "No")


### FIXED CODE ###

N = int(input())
A = int(input())

print("Yes" if N % 500 <= A else "No")
N, T = map(int, input().split())
L = [list(map(int, input().split())) for i in range(N)]

res = 10000

for i in range(N):
  if L[1] <= T:
    if res > L[0]:
      res = L[0]
     
if res == 10000:
  res = 'TLE'
print(res)

### FIXED CODE ###

N, T = map(int, input().split())
L = [list(map(int, input().split())) for i in range(N)]

res = 10000

for i in range(N):
  if L[i][1] <= T:
    if res > L[i][0]:
      res = L[i][0]
     
if res == 10000:
  res = 'TLE'
print(res)
from itertools import*
s=input()
k=int(input())
l=[]
for i in range(1,10):
    for t in range(len(s)+1-i):
        if len(set(s[t:t+i]))!=1:
            l.append(s[t:t+i])
for i in set(s):
    l.append(i)
print(sorted(set(l))[k-1])

### FIXED CODE ###

s=input()
k=int(input())
l=[]
for i in range(1,k+1):
    for t in range(len(s)-i+1):
        l.append(s[t:t+i])
print(sorted(set(l))[k-1])
N, M = map(int, input().split())

p_list = []
y_list = []
shi_map = {}

for i in range(M):
    p, y = map(int, input().split())
    p_list.append(p)
    y_list.append(y)
    if p in shi_map:
        shi_map[p].append(y)
    else:
        shi_map[p] = [y]
shi_map2 = {}
for k, v in shi_map.items():
    v = sorted(v)
    shi_map2[k] = v

for i in range(M):
    p = p_list[i]
    y = y_list[i]
    j = shi_map2[p].index(y)
    p_str = str(p).zfill(6)
    j_str = str(j+1).zfill(6)
    print(p_str + j_str)



### FIXED CODE ###

X, Y = map(int, input().split())

print(X + Y //2)
n, k, *A = map(int, open(0).read().split())
t = sum(A) / (n+k)
A = [a for a in A if int(a/t) >= 1]
X = []
for a in A:
    X.append(ceil(a / ceil(a/t)))
    X.append(ceil(a / int(a/t)))
X.sort()
print(X[k])

### FIXED CODE ###

from math import ceil
n, k, *A = map(int, open(0).read().split())
t = sum(A) / (n+k)
A = [a for a in A if int(a/t) >= 1]
c = k - sum(int(a/t)-1 for a in A)
X = []
for a in A:
    X.append(ceil(a / ceil(a/t)))
    X.append(ceil(a / int(a/t)))
X.sort()
print(X[-c-1])
X = int(input())
k = 1
n = 1

while true:
  ans = 360 * n % X
  if ans == 0:
    print(360 * n / X)
  else:
    n += 1


### FIXED CODE ###

X = int(input())
i = 1

while (360*i) % X != 0:
  i += 1
ans = 360*i//X
print(ans)