Harryxun/stf_run huggingface dataset:
from collections import deque

N = int(input())
tree = [[] for i in range(N)]
for i in range(N-1):
  a, b = map(int, input().split())
  tree[a-1].append(b-1)
  tree[b-1].append(a-1)

d = deque([[0, -1]])
dist = [0] * N
while d:
  node, par = d.pop()
  children = tree[node]
  for child in children:
    if child == par:
      continue
    dist[child] = (dist[node] + 1) % 2
    d.appendleft([child, node])

count0 = dist.count(0)
count1 = N - count0
s = [set(), set(), set()]
for i in range(1, N+1):
  s[i%3].add(i)
if count0 >= N//3:
  if count1 >= N//3:
    for i in range(N):
      if dist[i]:
        if s[2]:
          dist[i] = s[2].pop()
        else:
          dist[i] = s[0].pop()
      else:
        if s[1]:
          dist[i] = s[1].pop()
        else:
          dist[i] = s[0].pop()
  else:
    for i in range(N):
      if dist[i]:
        dist[i] = s[0].pop()
      else:
        if s[2]:
          dist[i] = s[2].pop()
        elif s[1]:
          dist[i] = s[1].pop()
        else:
          dist[i] = s[0].pop()
else:
  for i in range(N):
    if dist[i]:
      if s[2]:
        dist[i] = s[2].pop()
      elif s[1]:
        dist[i] = s[1].pop()
      else:
        dist[i] = s[0].pop()
    else:
      dist[i] = s[0].pop()

print(*dist)

### FIXED CODE ###

from collections import deque

N = int(input())
tree = [[] for i in range(N)]
for i in range(N-1):
  a, b = map(int, input().split())
  tree[a-1].append(b-1)
  tree[b-1].append(a-1)

d = deque([[0, -1]])
dist = [0] * N
while d:
  node, par = d.pop()
  children = tree[node]
  for child in children:
    if child == par:
      continue
    dist[child] = (dist[node] + 1) % 2
    d.appendleft([child, node])

count0 = dist.count(0)
count1 = N - count0
s = [set(), set(), set()]
for i in range(1, N+1):
  s[i%3].add(i)
if count0 > N//3:
  if count1 > N//3:
    for i in range(N):
      if dist[i]:
        if s[2]:
          dist[i] = s[2].pop()
        else:
          dist[i] = s[0].pop()
      else:
        if s[1]:
          dist[i] = s[1].pop()
        else:
          dist[i] = s[0].pop()
  else:
    for i in range(N):
      if dist[i]:
        dist[i] = s[0].pop()
      else:
        if s[2]:
          dist[i] = s[2].pop()
        elif s[1]:
          dist[i] = s[1].pop()
        else:
          dist[i] = s[0].pop()
else:
  for i in range(N):
    if dist[i]:
      if s[2]:
        dist[i] = s[2].pop()
      elif s[1]:
        dist[i] = s[1].pop()
      else:
        dist[i] = s[0].pop()
    else:
      dist[i] = s[0].pop()

print(*dist)
s = input()
k = int(input())
if (s[0] != '1'):
    print(s[0])
    exit(0)
first = s.find('1')
print(1) if k <= first or first == len(s) else print(s[first + 1])


### FIXED CODE ###

s = input()
k = int(input())
first = len(s)
for i in range(len(s)):
  if s[i] != '1': first = i; break
if s[0] != '1': print(s[0]); exit(0)
print(1) if k <= first else print(s[first])
N = int(input())
P = list(map(int, input().split()))
answer = []
count = []

for i in range(N):
    if P[i] <= min(P[0, i + 1]):
        answer.append[i]
print(len(answer))

### FIXED CODE ###

N = int(input())
P = list(map(int, input().split()))
answer = 0
minimum = P[0]

for i in range(N):
    if P[i] <= minimum:
        answer += 1
    minimum = min(P[i], minimum)
print(answer)
n = list(map(int, input().split()))
 
if n[0] > 10:
  print(l[1])
else:
  print(n[1] + 100*(10-n[0]))

### FIXED CODE ###

n = list(map(int, input().split()))
 
if n[0] > 10:
  print(n[1])
else:
  print(n[1] + 100*(10-n[0]))
N = int(input())
K = int(input())
X = int(input())
Y = int(input())
 
if  K > N:
	answer = (K * X) + (N - K) * Y:
else:
	answer = N * X
print(answer)   

### FIXED CODE ###

N = int(input())
K = int(input())
X = int(input())
Y = int(input())
 
if N <= K :
	answer = X * N
elif N >= K + 1:
	answer = (X * K) + (Y * (N - K) )
print(answer)
s=input()
s = s.split("/")
if s[0] < 2019:
    print("Heisei")
if s[0] == 2019 and s[1]<= "04":
    print("Heisei")
else:
    print("TBD")

### FIXED CODE ###

s = input()
 
if s <= '2019/04/30':
    print('Heisei')
else:
    print('TBD')
N=input()
Num = len(N)
if Num == 5:
		Ans = (int(N)-9999) + 900 + 9
elif Num == 4:
		Ans = 900 + 9
elif Num == 3:
		Ans = (int(N)-99) + 9
elif Num == 2:
		Ans = 9
elif Num == 1:
		Ans = N
print(Ans)

### FIXED CODE ###

N=input()
Num = len(N)
if Num == 5:
		Ans = (int(N)-9999) + 900 + 9
elif Num == 4:
		Ans = 900 + 9
elif Num == 3:
		Ans = (int(N)-99) + 9
elif Num == 2:
		Ans = 9
elif Num == 1:
		Ans = N
elif Num == 6:
  Ans = 90000 + 900 + 9
print(Ans)
n=int(input())
s=list(input(i) for i in range(n))

counter = Counter(s)
max_cnt = max(counter.values())
names = [name for name, cnt in counter.items() if cnt == max_cnt]
names.sort()

print(*names, sep='\n')

### FIXED CODE ###

from collections import Counter

stdin = open(0)
N = int(stdin.readline())
S = stdin.read().split()

counter = Counter(S)
max_cnt = max(counter.values())
names = [name for name, cnt in counter.items() if cnt == max_cnt]
names.sort()

print(*names, sep='\n')
n = int(input())
a = list(map(int, input().split()))
order = []
for i in range(1, n+1):
    order += [a.index(i)+1]
print(' '.join(map(str, order)))

### FIXED CODE ###

n = int(input())
li = range(1, n+1)
odd = 0
for i in li:
    if i % 2 == 1:
        odd += 1
ans = odd / n
print(ans)
S = input()
p = 10**9 + 7

N = len(S)
dp = [[0 for _ in range(13)] for _ in range(N + 1)]
dp[N][0] = 1 # i = N - 1のケースでうまくいくための処置

for i in range(N - 1,  -1,  -1):  # 小さい桁から順に
    w = 1 if i == N - 1 else (w * 10) % 13 # 各桁の重み

    if S[i] is not '?':
        k = int(S[i])
        for j in range(13):
            dp[i][(j + w * k) % 13] = dp[i + 1][j]
    else:
        for j in range(13):
            for k in range(10): # ?の値が0, 1, ..., 9のとき
                dp[i][(j + w * k) % 13] = (dp[i][(j + w * k) % 13] + dp[i + 1][j]) % p

print(dp[0][5])


### FIXED CODE ###

p = 10**9 + 7
S = input()
N = len(S)

dp = [[0 for _ in range(13)] for _ in range(2)]
dp[0][0] = 1 # i = N - 1のケースでうまくいくための処置
r = 0

for i in range(N - 1,  -1,  -1):  # 小さい桁から順に
    w = 1 if i == N - 1 else (w * 10) % 13 # 各桁の重み
    r = 1 - r  # dpの0行目と1行目を交互に使う
    if S[i] == '?':
        for j in range(13):
            for k in range(10): # ?の値が0, 1, ..., 9のとき
                dp[r][(j + w * k) % 13] += dp[1 - r][j]
                if dp[r][(j + w * k) % 13] >= p:
                    dp[r][(j + w * k) % 13] -= p
    else:
        k = int(S[i])
        for j in range(13):
            dp[r][(j + w * k) % 13] = dp[1 - r][j]

    dp[1 - r] = [0] * 13

print(dp[r][5])
import numpy as np
n,m = map(int,input().split())

li = np.array([i for i in range(1,n+1)])
for i in range(m):
  l,r = map(int,input().split())
  li = li[l <= li]
  li = li[li <= r]
  if len(li)==0:
    break
else:
  print(len(li))
  exit()
print(0)

### FIXED CODE ###

n,m = map(int,input().split())

lans = 1
rans = n
for i in range(m):
  l,r = map(int,input().split())
  lans = max(lans,l)
  rans = min(rans,r)
if lans <= rans:
  print(len(list(range(lans,rans+1))))
else:
  print(0)
n = input()
print((n+1)//2)

### FIXED CODE ###

n = int(input())
print((n+1)//2)
A = []
for i in range(3):
  a = input().split()
  a = [int(num) for num in a]
  A.append(a)

N = int(input())
b = [int(input()) for i in range(N)]

for i in range(3):
  for j in range(3):
    if b.count(A[i][j]) != 0:
      A[i][j] = 0
    else:
      continue

if A[1][1] == 0:
  if A[0][0]==A[2][2]==0 or A[0][2]==A[2][0]==0:
    print("Yes")
  else:
    print("No")
elif A[1][1] != 0:
  if sum(A[0])==0 or sum(A[2])==0 or sum(A[:][0])==0 or sum(A[:][2]==0):
    print("Yes")
  else:
    print("No")

### FIXED CODE ###

A = []
for i in range(3):
  a = input().split()
  a = [int(num) for num in a]
  A.append(a)

N = int(input())
b = [int(input()) for i in range(N)]

for i in range(3):
  for j in range(3):
    if b.count(A[i][j]) != 0:
      A[i][j] = 0
    else:
      continue

def Agetraw(j):
    Ans = [int(A[i][j]) for i in range(3)]
    return(Ans)

if (sum(A[0])==0 or sum(A[1])==0 or sum(A[2])==0 
    or sum(Agetraw(0))==0 or sum(Agetraw(1))==0 or sum(Agetraw(2))==0 
    or A[0][0]+A[1][1]+A[2][2]==0 or A[0][2]+A[1][1]+A[2][0]==0):
  print("Yes")
else:
  print("No")
S = input()
print('Heisei' if S <= '2019/04/30' else 'TBD)

### FIXED CODE ###

S = input()
print('Heisei' if S <= '2019/04/30' else 'TBD')
z = ""
for x in raw_input():
    if x.islower():
        z += x.upper()
    else:
        z += x.lower(),

print z

### FIXED CODE ###

z = ""
for x in raw_input():
    if x.islower():
        z += x.upper()
    else:
        z += x.lower()

print z
import bisect
import sys
sys.setrecursionlimit(10**9)

def main():
    S, T = list(input()),list(input())

    len_of_S = len(S)
    counter = {}
    seen = set()
    for i in range(len_of_S):
        if S[i] in seen:
            counter[S[i]].append(i) # 常に単調増加
        else:
            counter[S[i]] = [i]
            seen.add(S[i])

    len_of_T = len(T)

    if not T[0] in seen:
        print(-1)
        exit()

    counts = counter[T[0]]
    if len(counts) == 0:
        print(-1)
        exit()

    pre = counts[0]
    rep = 1

    for i in range(1,len_of_T):
        counts = counter[T[i]]
        if len(counts) == 0:
            print(-1)
            exit()

        j = bisect.bisect_left(counts,pre)
        mx = len(counts)

        while j < mx and not counts[j] > pre:
            j += 1

        # print(pre,ans)
        if j<mx:
            pre = counts[j]
        else:
            pre = counts[0]
            rep += 1
        # print(pre,ans)

    # print(counter[T[::-1][0]],len_of_S)
    rep -= 1
    ans = rep * len_of_S  + counter[T[::-1][0]][0] + 1
    print(ans)




if __name__ == "__main__":
  main()


### FIXED CODE ###

import bisect
import sys
sys.setrecursionlimit(10**9)

def main():
    S, T = list(input()),list(input())

    len_of_S = len(S)
    counter = {}
    seen = set()
    for i in range(len_of_S):
        if S[i] in seen:
            counter[S[i]].append(i) # 常に単調増加
        else:
            counter[S[i]] = [i]
            seen.add(S[i])

    len_of_T = len(T)

    if not T[0] in seen:
        print(-1)
        exit()

    counts = counter[T[0]]
    if len(counts) == 0:
        print(-1)
        exit()

    pre = counts[0]
    rep = 1

    for i in range(1,len_of_T):
        if not T[i] in seen:
            print(-1)
            exit()

        counts = counter[T[i]]
        if len(counts) == 0:
            print(-1)
            exit()

        j = bisect.bisect_left(counts,pre)
        mx = len(counts)

        while j < mx and not counts[j] > pre:
            j += 1

        # print(pre,rep)
        if j<mx:
            pre = counts[j]
        else:
            pre = counts[0]
            rep += 1
        # print(pre,rep)

    # print(counter[T[::-1][0]],len_of_S)
    rep -= 1
    ans = rep * len_of_S  + pre + 1
    print(ans)




if __name__ == "__main__":
  main()
n=int(input())
s=input()

ans=0
for i in range(2,n)
	x=set(list(s[:i]))
	y=set(list(s[i:]))
	sum=x&y
	ans=max(ans,len(sum))

print(ans)

### FIXED CODE ###

n=int(input())
s=input()

ans=0
for i in range(2,n):
	x=set(list(s[:i]))
	y=set(list(s[i:]))
	sum=x&y
	ans=max(ans,len(sum))

print(ans)
n,k=map(int,input().split())
A=list(map(int,input().split()))

l=-1
r=max(A)+1
while r-l>1:
  m=(l+r)//2
  cut=0
  
  for i in range(n):
    cut+=((A[i]+m-1)//m)-1
  if cut>k:
    l=m
  else:
    r=m
print(r)
  

### FIXED CODE ###

n,k=map(int,input().split())
A=list(map(int,input().split()))

l=0
r=max(A)+1
while r-l>1:
  m=(l+r)//2
  cut=0
  
  for i in range(n):
    cut+=((A[i]+m-1)//m)-1
  if cut>k:
    l=m
  else:
    r=m
print(r)
while True:
    N = int(input())
    if N == 0:
        break
    a = list(map(int, input().split()))

    ## dp[i][j]: i???????????°????????§??§j????????????????????°
    dp = [[0 for j in range(21)] for i in range(N-1)]

    dp[0][a[0]] = 1
    for i in range(1, N-1):
        for j in range(21):
            if (j - a[i]) in range(21):
                dp[i][j] += dp[i-1][j-a[i]]
            if (j + a[i]) in range(21):
                dp[i][j] += dp[i-1][j+a[i]]
            
    print(dp[N-2][a[N-1]])

### FIXED CODE ###

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

## dp[i][j]: i???????????°????????§??§j????????????????????°
dp = [[0 for j in range(21)] for i in range(N-1)]

dp[0][a[0]] = 1
for i in range(1, N-1):
    for j in range(21):
        if (j - a[i]) in range(21):
            dp[i][j] += dp[i-1][j-a[i]]
        if (j + a[i]) in range(21):
            dp[i][j] += dp[i-1][j+a[i]]
        
print(dp[N-2][a[N-1]])
n, d = map(int, input().split())
x = [list(map(int, input().split())) for i in range(n)]
cnt = 0
for i in range(n):
  for j in range(i+1, n):
    a = x[i]
    b = x[j]
    z = 0
    for k in range(d):
      z += (a[k] - b[k]) ** 2
    if math.sqrt(z) % 1 == 0:
      cnt += 1
print(cnt)

### FIXED CODE ###

import math

n, d = map(int, input().split())
x = [list(map(int, input().split())) for i in range(n)]
cnt = 0
for i in range(n):
  for j in range(i+1, n):
    a = x[i]
    b = x[j]
    z = 0
    for k in range(d):
      z += (a[k] - b[k]) ** 2
    if math.sqrt(z) % 1 == 0:
      cnt += 1
print(cnt)
N = int(input())
A = map(int, input().split())
B = map(int, input().split())
C = map(int, input().split())
add_s = 0
for order in range(N-1):
  cur_f = A[order]
  nxt_f = A[order+1]
  add_s += C[order] if nxt_f == cur_f + 1 else 0
  
print(sum(B) + add_s)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
add_s = 0
for idx in range(N-1):
  cur_f = A[idx]
  nxt_f = A[idx+1]
  add_s += C[cur_f-1] if nxt_f == cur_f + 1 else 0

print(sum(B) + add_s)
X, N = map(int, input().split())
p = list(map(int, input().split()))

if len(p) == 0:
    print(X)
    exit()

if not X in p:
    print(X)
    exit()

small = [i for i in range(-1, X)]
big = [i for i in range(X+1, 101)]
small.reverse()
print(small)
print(big)
print(max(len(big),len(small)))
for i in range(max(len(big),len(small))):
    if not small[i] in p:
        print(small[i])
        exit()
    elif not big[i] in p:
        print(big[i])
        exit()

### FIXED CODE ###

X, N = map(int, input().split())
p = list(map(int, input().split()))

if len(p) == 0:
    print(X)
    exit()

if not X in p:
    print(X)
    exit()

small = [i for i in range(-101, X)]
big = [i for i in range(X+1, 102)]
small.reverse()
for i in range(max(len(big),len(small))):
    if not small[i] in p:
        print(small[i])
        exit()
    elif not big[i] in p:
        print(big[i])
        exit()
N,M = list(map(int,input().strip().split()))
K = N//2
ans = []
left = 1
right = K
while left<right:
    ans += [(left,right)]
    left+=1
    right-=1

left = K+1
right = N
if (right-left)%2 == (K-1)%2:
    right -= 1
while left<right:
    ans += [(lfet,right)]
    left += 1
    right -= 1

for i in range(M):
    print(ans[i][0],ans[i][1])


### FIXED CODE ###

N,M = list(map(int,input().strip().split()))

K = N//2
ans = []

if N == 3:
    ans = [(1,2)]
elif N == 4:
    ans = [(1,2)]
elif N == 5:
    ans = [(1,2),(3,5)]
else:
    left = 1
    right = K
    while left<right:
        ans += [(left,right)]
        left+=1
        right-=1

    left = K+1
    right = N
    if (right-left)%2 == (K-1)%2:
        right -= 1
    while left<right:
        ans += [(left,right)]
        left += 1
        right -= 1

for i in range(M):
    print(ans[i][0],ans[i][1])
while True:
    H, W =[int(i) for i in input().split()]
    if H == w == 0:
        break

    for h in range(h):
        for w in range(w):
            print('w', end='')
        
        print()

    print()

### FIXED CODE ###

while True:
    H, W =[int(i) for i in input().split()]
    if H == W == 0:
        break

    for h in range(H):
        for w in range(W):
            print('#', end='')
        
        print()

    print()
S = input()
if(S=="Sunny"):
    print("Cloudy")
elif(S=="Cloudy"):
    print("Rainy")
elif(S=="Rainy"):
    print(Sunny)

### FIXED CODE ###

S = input()
if(S=="Sunny"):
    print("Cloudy")
elif(S=="Cloudy"):
    print("Rainy")
elif(S=="Rainy"):
    print("Sunny")
x,y = map(int,input().split())
if y == x:
    print(0)
else:
    if abs(y) >= abs(x):
        tmp = abs(y)-abs(x)
        if x>=0 and y>=0:
            print(tmp)
        elif x>=0 and y<0:
            print(tmp+1)
        elif x<0 and y>=0:
            print(tmp+1)
        else:
            print(abs(y)-x+1)
    else:
        if x>=0 and y>=0:
            print(x+y+1)
        elif x>=0 and y<0:
            print(x+y+1)
        elif x<0 and y>=0:
            print(y-x)
            print(1/0)
        else:
            print(y-x)

### FIXED CODE ###

x,y = map(int,input().split())
if y == x:
    print(0)
elif y == 0:
    if x > 0:
        print(x+1)
    else:
        print(-x)
else:
    if abs(y) >= abs(x):
        tmp = abs(y)-abs(x)
        if x>=0 and y>=0:
            print(tmp)
        elif x>=0 and y<0:
            print(tmp+1)
        elif x<0 and y>=0:
            print(tmp+1)
        else:
            print(tmp+2)
    else:
        if x>=0 and y>=0:
            print(-y+x+2)
        elif x>=0 and y<0:
            print(x+y+1)
        elif x<0 and y>=0:
            print(-y-x+1)
        else:
            print(y-x)
def popcount(x):
    bitx = bin(x)
    cnt = bitx.count('1')
    return cnt

n = int(input())
x = list(input())
for i in range(n):
    tmp = x.copy()
    if tmp[i] == '1':
        tmp[i] = '0'
    else:
        tmp[i] = '1'
    tmp = int(''.join(tmp), 2)
    tmp2 = popcount(tmp)
    if tmp % tmp2 == 0:
        print(1)
    elif tmp % 2 != 0 and tmp2 % 2 == 0:
        print(3)
    else:
        print(2)

### FIXED CODE ###

import sys
# import math
# import bisect
# import numpy as np
# from decimal import Decimal
# from numba import njit, i8, u1, b1 #JIT compiler
# from itertools import combinations, product
# from collections import Counter, deque, defaultdict

# sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_ints2(x):   return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def GCD(a: int, b: int) -> int: return b if a%b==0 else GCD(b, a%b)
def LCM(a: int, b: int) -> int: return (a * b) // GCD(a, b)

def popcount(num):
    cnt = 0
    while num > 0:
        num %= bin(num).count('1')
        cnt += 1
    return cnt

def Main():
    n = read_int()
    x = read_str()
    x_int = int(x, 2)

    cnt = x.count('1')
    minus_cnt = cnt - 1
    plus_cnt = cnt + 1
    
    minus_mod = x_int % minus_cnt if minus_cnt != 0 else 0
    plus_mod = x_int % plus_cnt

    for i in range(n):
        if x[i] == '0':
            print(popcount((plus_mod + pow(2, n - 1 - i, plus_cnt)) % plus_cnt) + 1)
        elif minus_cnt != 0:
            print(popcount((minus_mod - pow(2, n - 1 - i, minus_cnt)) % minus_cnt) + 1)
        else:
            print(0)

if __name__ == '__main__':
    Main()
import math

A, B, C, D = (int(i) for i in input().split())

if C == D:
    duplicate = C
elif C > D and C % D == 0:
    duplicate = C
elif D > C and D % C == 0:
    duplicate = D
else:
    duplicate = C * D // math.gcd(C, D)

cCnt = (B - A) // C
dCnt = (B - A) // D
duplicateCnt = (B - A) // duplicate

print(B - A - cCnt - dCnt + duplicateCnt)

### FIXED CODE ###

import sys

input = sys.stdin.readline


class AtCoder:
    def main(self):
        A, B, C, D = map(int, input().split())

        def gcd(a, b):
            while b:
                a, b = b, a % b
            return a

        def lcm(a, b):
            return a * b // gcd(a, b)

        def f(x):
            return x - (x // C + x // D - x // lcm(C, D))

        print(f(B) - f(A - 1))


# Run main
if __name__ == '__main__':
    AtCoder().main()
import sys
S = input[0]
T = input[1]
leng　= len(S)
int N = 0

for i in leng:
  if S.charAt(i) == T.charAt(j):
    N = N + 1

print (N)

### FIXED CODE ###

S = input()
T = input()
 
c = 0
 
for s,t in zip(S,T):
  if s != t:
    c += 1
print(c)
def pi(a,p):
  c=0
  pi=0
  while c>2:
    c=a*3+p
    pi=c//2
    
   return pi

### FIXED CODE ###

a,p=map(int,input().split())
c=(a*3)+p
pi=c//2
print(str(pi)+'\n')
input = raw_input

def init():
    table = [True] * 2000001
    table[0] = False
    table[1] = False
    n = len(table)
    for i in range(2, n):
        for j in range(i + i, n, i):
            table[j] = False
    return table
    
def is_prime(p):
    if p == 0 or p == 1:
        return False
    for i in range(2, p - 1):
        if p % i == 0:
            return False
    return True

def solve(price, ps, is_prime):
    dp = []
    for i in range(len(ps)):
        dp.append([False] * (price + 1))

    dp[0][ps[0]] = True
    dp[0][0]     = True

    for i in range(1, len(ps)):
        for p in range(price + 1):
            if p >= ps[i]:
                dp[i][p] = dp[i - 1][p] or dp[i][p - ps[i]]
            else:
                dp[i][p] = dp[i - 1][p]

    p = -1
    for i in range(0, price + 1):
        if is_prime[i] and dp[len(ps) - 1][i]:
            p = i
    if p == -1:
        print("NA")
    else:
        print(p)
    
def main():
    table = init()
    while True:
        n, price = map(int,input().split())
        if n == 0 and price == 0:
            return
        ps = []
        for i in range(n):
            ps.append(int(input()))
        solve(price, ps, table)

main()

### FIXED CODE ###

from datetime import datetime
import math

def measure(f):
    measure_start = datetime.now()
    v = f()
    print(datetime.now() - measure_start)
    return v

input = raw_input
range = xrange
    
def init():
    table = [True] * 1000001
    table[0] = False
    table[1] = False
    n = len(table)

    def prime(p):
        for i in range(p + p, n, p):
            table[i] = False
    prime(2)
    prime(3)
    prime(5)
    prime(7)
    prime(11)
    prime(13)

    for i in range(2, int(math.sqrt(n) + 1)):
        if (i % 2 != 0 and i % 3 != 0 and i % 5 != 0 and
            i % 7 != 0 and i % 11 != 0 and i % 13 != 0):
            for j in range(i * i, n, i):
                table[j] = False
#    for i in range(len(table)):
#        if table[i]:
#            print(i)
    return table
    
def solve(price, ps, is_prime):
    dp = [0] * ((price >> 5) + 1)

    for i in range(0, price + 1,ps[0]):
        dp[i >> 5] |= 1 << (i & 31)
    dp[0] = 1
    
    for i in range(1, len(ps)):
        cur_p = ps[i]
        r = cur_p & 31
        rest = 0
        if cur_p >= 32:
            for p in range(cur_p, price + 1, 32):
                i1 = (p - cur_p) >> 5
                i2 = p >> 5
                v = dp[i1]
                dp[i2] |= (v << r) | rest
                rest = (v >> (32 - r)) & ((1 << r) - 1)
        else:
            for p in range(cur_p, price + 1):
                dp[p >> 5] |= (dp[(p - cur_p) >> 5] >> ((p - cur_p) & 31) & 1) << (p & 31)
            
    p = -1
    for i in range(0, price + 1):
        if is_prime[i] and (dp[i >> 5] >> (i & 31)) & 1 == 1:
            p = i
    if p == -1:
        print("NA")
    else:
        print(p)
    
def main():
    table = init()
    while True:
        n, price = map(int,input().split())
        if n == 0 and price == 0:
            return
        ps = []
        for i in range(n):
            ps.append(int(input()))
        solve(price, ps, table)

main()
a= input()
i=0
while i< len(s):
  j=s[i:i+1]
  if j==7:
    print('Yes')
    break
  i+=1

### FIXED CODE ###

s= input()
i=0
res=[]
while i< len(s):
  j=s[i:i+1]
  res.append(j)
  i+=1
print('Yes' if str(7) in res else 'No')
import math
a = 0
b = 1
N, D = map(int, input().split())
ls = [list(map(int, input().split()))for i in range(N)]
for i in range(N):
    for j in range(i, N):
        for k in range(D):
            a += (ls[i][k] - ls[j][k]) ** 2
            if math.sqrt(a).is_integer() is True:
                b += 1

print(b)


### FIXED CODE ###

N, A, B = map(int, input().split())

if N * A >= B:
    print(B)
else:
    print(N * A)