Harryxun/stf_run huggingface dataset:
#dj 16D8101012J ito jun
def search(a,b):
    na=len(a)
    nb=len(b)
    array = [[0]*(nb+1) for _ in range(na+1)]
    for i,x in enumerate(a,1):
        prerow=array[i-1]
        row=array[i]
        for j,y in enumerate(b,1):
            if x == y:
                row[j]=prerow[j-1]+1
            elif prerow[j] < row[j-1]+1:
                row[j] = row[j-1]
            else:
                row[j] = prerow[j]
    return array[-1][-1]

n = int(input())
strs = [list(i) for i in input()]
result = [search(strs[i*2], strs[i*2+1]) for i in range(n)]
print(*result, sep="\n")



### FIXED CODE ###

#dj 16D8101012J ito jun
import sys
def search(a,b):
    na=len(a)
    nb=len(b)
    array = [[0]*(nb+1) for _ in range(na+1)]
    for i,x in enumerate(a,1):
        prerow=array[i-1]
        row=array[i]
        for j,y in enumerate(b,1):
            if x == y:
                row[j]=prerow[j-1]+1
            elif prerow[j] < row[j-1]:
                row[j] = row[j-1]
            else:
                row[j] = prerow[j]
    return array[-1][-1]

n = int(input())
strs = [list(i) for i in sys.stdin.read().splitlines()]
result = [search(strs[i*2], strs[i*2+1]) for i in range(n)]
print(*result, sep="\n")
while True:
    i = 2
    ok = True
    while i * i <= x:
        if x % i == 0:
            ok = False
            break
        i += 1
    if ok:
        print(x)
        break
    x += 1

### FIXED CODE ###

import math
X = int(input())


def get_primenumber(number):
    prime_list = []
    # 2からnumberまでの数字をsearch_listに入れる
    search_list = list(range(2, number+1))
    while True:
    # search_listの先頭の値が√nの値を超えたら処理終了
        if search_list[0] > math.sqrt(number):
            # prime_listにsearch_listを結合
            prime_list.extend(search_list)
            break
        else:
            # search_listの先頭をprime_listに入れる
            head_num = search_list[0]
            prime_list.append(head_num)
            # search_listの先頭をpopする
            search_list.pop(0)
            # head_numの倍数を取り除く
            search_list = [num for num in search_list if num % head_num != 0]
    return prime_list

prime_list = get_primenumber(100000)

left = 0
right = len(prime_list)-1

if X == 2:
    print(int(2))
elif X > 99991:
    print(int(100003))
else:
    while left <= right:
        mid = (left+right) // 2
        if prime_list[mid] == X:
            ans = prime_list[mid]
            break
        elif prime_list[mid] > X:
            if prime_list[mid-1] < X:
                ans = prime_list[mid]
                break
            else:
                right = mid - 1
        else:
            if prime_list[mid+1] > X:
                ans = prime_list[mid+1]
                break
            else:
                left = mid + 1

    print(int(ans))
import sys

def solve(a, b, c):
    # Uncomment the following if you want to check the input.
    # print('a =', a)
    # print('b =', b)
    # print('c =', c)
    w=[a,b,c]
    if 5 and 7 not in w:
        return ('NO')
    e=w.count(5)
    if e==2:
        return ('YES')
    else:
        return ('NO')


def readQuestion():
    ws = sys.stdin.readline().strip().split()
    a = int(ws[0])
    b = int(ws[1])
    c = int(ws[2])
    return (a, b, c,)

def main():
    solve(*readQuestion())

# Uncomment before submission
 main()

### FIXED CODE ###

a,b,c=input().split()
w=[a,b,c]
e=w.count('5')
if '5' and '7' not in w:
    print ('NO')
elif e==2:
    print ('YES')
else:
    print ('NO')
import sys
N=input()

for i in range(1,9):
    a=N//i
    b=N%i
    if (0<a<10 && b==0):
        print("Yes")
        break
else print("No")

### FIXED CODE ###

import sys
X=input()
N=int(X)

for i in range(1,10):
    a=N//i
    b=N%i
    if (0<a<10 and b==0):
        print("Yes")
        break
else:
     print("No")
string=input()
first=string[0]
last=string[len(string)-1]
mid=str(len(string[1:len(string-1)]))
print(first+mid+last)

### FIXED CODE ###

string=input('')
first=string[0]
last=string[len(string)-1]
mid=str(len(string[1:len(string)-1]))
print(first+mid+last)
a=int(input())
b=int(input())
c=a*b
if c%2==0:
  print("Even")
else:
  print("Odd")

### FIXED CODE ###

a,b=map(int,input().split())
c=a*b
if c%2==0:
  print("Even")
else:
  print("Odd")
X, K, D = map(int, input().split())
X=abs(X)
if X==0 and K%2==0:
    ans=0
elif X==0 and K%2==1:
    ans=D
elif D>=X and K%2==0:
    ans=X
elif D>=X and K%2==1:
    ans=D-X
elif X>0 and D<X :
    if K*D<X:
        ans=X-K*D
    else:
        for i in range(0,K):
            if X-i*D<0:
                if (K-i)%2==0:
                    ans=X-(i-1)*D
                    break
                else:
                    ans=i*D-X
                    break
print(ans)

### FIXED CODE ###

X, K, D = map(int, input().split())
X=abs(X)
if D>=X and K%2==0:
    ans=X
elif D>=X and K%2==1:
    ans=D-X
elif D<X and K*D<X:
    ans=X-K*D
else:
    ans=X%D
    if (X-ans)%2!=K%2:
        ans=D-ans
print(ans)
def resolve():
    a = input()
    b = input()
    c = input()
    d = {"a": a, "b": b, "c": c}
    now = d["a"][0]
    d["a"] = d["a"][1:]
    next = d[now][0]
    while True:
        if len(d[next]) == 0:
            print(next.upper())
            return 0
        next = d[next][0]
        d[next] = d[next][1:]


if __name__ == "__main__":
    resolve()


### FIXED CODE ###

def resolve():
    a = list(input())
    b = list(input())
    c = list(input())
    d = {"a": a, "b": b, "c": c}
    now = "a"
    while d[now]:
        now = d[now].pop(0)
    print(now.upper())


if __name__ == "__main__":
    resolve()
if S[-1] == s:
  print(S + "es")
else:
  print(S + "s")
  

### FIXED CODE ###

S = input()
if S[-1] == "s":
  print(S + "es")
else:
  print(S + "s")
# あなたは、500円玉をA枚、100円玉をB枚、50円玉をC枚持っています。 これらの硬貨の中から何枚かを選び、合計金額をちょうどX円にする方法は何通りありますか。
A,B,C,X=map(int,input().split())
# A,B,C,X=map(int,'30 30 30 12000'.split())
N=0

for i in range(A+1):
    for j in range(B+1):
        for k in range(C+1):
            if i*500+j*100+k*50==X:
                N+=1

print(N)

### FIXED CODE ###

A = int(input())
B = int(input())
C = int(input())
X = int(input())

N=0

for i in range(A+1):
    for j in range(B+1):
        for k in range(C+1):
            if i*500+j*100+k*50==X:
                N+=1

print(N)
a = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
index = input()
print(a[index-1])

### FIXED CODE ###

a = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
index = int(input()) -1
print(a[index])
n = int(input())
 
numbers = list(map(int, input().split(' ')))
approved = False
 
for num in numbers:
  if (num % 2 == 0):
  	if (num % 3 == 0) or (num % 5 == 0):
      approved = True
      continue
  	else:
      approved = False
      print('DENIED')
      break
if approved:
  print('APPROVED')

### FIXED CODE ###

n = int(input())
 
numbers = list(map(int, input().split(' ')))
approved = True
 
for num in numbers:
  if (num % 2 == 0):
    if (num % 3 == 0) or (num % 5 == 0):
      approved = True
      continue
    else:
      approved = False
      print('DENIED')
      break
if approved:
  print('APPROVED')
def main():
  S=input()
  N=len(S)
  s=0
  for i in range(N//2):
      if S[i]!=S[N-1-i]:
        S[N-1-i]=S[i]
        s+=1
  print(s)
main()

### FIXED CODE ###

def main():
  S=input()
  s=0
  N=len(S)
  for i in range(N//2):
    if S[i]!=S[N-1-i]:
      s+=1
  print(s)
main()
def f(N,h,n):
    return 4/N - 1/h - 1/n

N = int(input())
for h in range(1, 5):
    for n in range(1, 5):
        tmp = f(N, h, n)
        if tmp != 0:
            w = 1/tmp
            if w.is_integer():
                ans = [h,n,int(w)]
                break
print(*ans)

### FIXED CODE ###

N = int(input())
for h in range(1, 3501):
    for n in range(1, 3501):
        div = 4*h*n - N*(h+n)
        if div!=0 and N*h*n%div==0:
            w = N*h*n // div
            if w > 0:
                print(h,n,w)
                exit()
lis=list(map(int,input().split()))
mod=(10**9)+7
import math
for i in range(1,lis[1]+1):
    #ans=int(math.factorial(lis[0]-lis[1]+1)/(math.factorial(i)*math.factorial(lis[0]-lis[1]-i+1)))%mod
    #ans*=int(math.factorial(lis[1]-1)/(math.factorial(i-1)*math.factorial(lis[1]-i)))%mod
    ans=int((math.factorial(lis[0]-lis[1]+1)*(math.factorial(lis[1]-1)))/(math.factorial(i)*math.factorial(lis[0]-lis[1]-i+1)*math.factorial(i-1)*math.factorial(lis[1]-i)))%mod
    print(ans)


### FIXED CODE ###

lis=list(map(int,input().split()))
mod=(10**9)+7
pascal=[]
#print(lis[0]-lis[1]+1,lis[1]-1)
rank=max(lis[0]-lis[1]+1,lis[1]+1)
for i in range(rank):
    pascal.append([])
    for j in range(i+2):
        if j==0 or j==i+1:
            pascal[i].append(1)
        else:
            pascal[i].append(pascal[i-1][j-1]+pascal[i-1][j])
#print(len(pascal[-1]))
for i in range(1,1+lis[1]):
    if i<=lis[0]-lis[1]+1:
        ans=pascal[lis[0]-lis[1]][i]*pascal[lis[1]-2][i-1]%mod
    else:
        ans=0
    print(ans)
n= int(input())
r= int(input())

if n<10:
    print(r - 100 * (10-n) )
else:
    print(r)

### FIXED CODE ###

input= list( map(int,input().split()) )
n = input[0]
r=  input[1]

if n<10:
    print(r + (100 * (10-n)) )
else:
    print(r)
import sys

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

sys.setrecursionlimit(n+1)

def f(x):
    if x == 0:
        return 1
    else:
        return f(x-1) * x

for i in range(1, k+1):
    if n-k+1 < i:
        print(0)
        continue
    print(int((f(n-k+1)/(f(i)*f(n-k+1-i)) * f(k-1)/(f(i-1)*f(k-i))) % (10**9 + 7)))


### FIXED CODE ###

def main():
    n, k = map(int, input().split())

    mod = 10 ** 9 + 7
    fact = [1]
    for i in range(1, 2001):
        fact.append(fact[-1] * i)

    def comb(l, r):
        return fact[l] // fact[r] // fact[l - r]

    for i in range(1, k + 1):
        print((comb(n - k + 1, i) * comb(k - 1, i - 1)) % mod)


if __name__ == "__main__":
    main()
N = int(input())
K = int(input())
a = 1
for _ in range(N):
    a = min(a*2, a+k)
print(a)

### FIXED CODE ###

N = int(input())
K = int(input())
a = 1
for _ in range(N):
    a = min(a*2, a+K)
print(a)
def sort(str_list):
  for i in range(len(str_list) - 1):
    string = str_list[i]
    for j in range(i + 1, len(str_list)):
      next_string = str_list[j]
      for k in range(len(string)):
        if ord(string[k]) > ord(next_string[k]):
          temp = string
          str_list[i] = next_string
          str_list[j] = temp
          break
        elif ord(string[k]) == ord(next_string[k]):
          continue
        else:
          break
  ans = ""
  for i in str_list:
    ans += i
  return ans

line1 = input().split()
n = line1[0]
l = line1[1]
str_list = []
for i in range(n):
  str_list.append(input())
print(sort(str_list))
  

### FIXED CODE ###

def order(str1, str2):
  for i in range(len(str1)):
    if ord(str1[i]) > ord(str2[i]):
      return False
    elif ord(str1[i]) == ord(str2[i]):
      continue
    else:
      return True
 
def sort(str_list):
  for i in range(len(str_list) - 1):
    for j in range(i + 1, len(str_list)):
      if not order(str_list[i], str_list[j]):
        temp = str_list[i]
        str_list[i] = str_list[j]
        str_list[j] = temp
  ans = ""
  for i in str_list:
    ans += i
  return ans
 
line1 = input().split()
n = int(line1[0])
l = line1[1]
str_list = []
for i in range(n):
  str_list.append(input())
print(sort(str_list))
n = int(input())
a_list = list(map(int, input().split()))
b_list = list(map(int, input().split()))
c_list = list(map(int, input().split()))

score = 0

for val in b_list :
	score +=val
	
for val in range(n-1):
	if a_list[val+1] - a_list[val] == 1:
		score += c_list[a_list[val-1]]
	else:
		pass

print(score)


### FIXED CODE ###

n = int(input())
a_list = list(map(int, input().split()))
b_list = list(map(int, input().split()))
c_list = list(map(int, input().split()))

score = 0

for val in b_list :
	score +=val
	
for val in range(n-1):
	if a_list[val+1] - a_list[val] == 1:
		score += c_list[a_list[val]-1]
	else:
		pass

print(score)
a,b,c = map(int,input().split())

if a<b<c:
  print 'yes'
else:
  print 'no'

### FIXED CODE ###

a,b,c = map(int,raw_input().split())

if a<b and b<c:
  print 'Yes'
else:
  print 'No'
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from itertools import groupby
import sys
def main(s, x, y):
    g = [x, y]
    o = [[], []]

    direction = count = 0
    first = True
    for c in s:
        if c == 'T':
            if first:
                g[0] -= count
                first = False
            elif count > 0:
                o[direction].append(count)
            count = 0
            direction ^= 1
        else:
            count += 1
    if first:
        g[0] -= count
    elif count > 0:
        o[direction].append(count)

    for d in range(2):
        l = o[d]
        M = sum(l)
        M2 = M * 2
        if abs(g[d]) > M:
            print('No')
            return
        pre = [False] * (M2 + 1)
        pre[M] = True
        for i, v in enumerate(l):
            dp = [False] * (M2 + 1)
            for a in range(M2 + 1):
                if pre[a] == False: continue
                if a >= v:
                    dp[a - v] = True
                if a + v <= M2:
                    dp[a + v] = True
            pre = dp
        if dp[g[d] + M] == False:
            print('No')
            return
    print('Yes')

if __name__ == '__main__':
    input = sys.stdin.readline
    s = input().rstrip()
    x, y = map(int, input().split())
    main(s, x, y)


### FIXED CODE ###

# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from itertools import groupby
import sys
def main(s, x, y):
    g = [x, y]
    o = [[], []]

    direction = count = 0
    first = True
    for c in s:
        if c == 'T':
            if first:
                g[0] -= count
                first = False
            elif count > 0:
                o[direction].append(count)
            count = 0
            direction ^= 1
        else:
            count += 1
    if first:
        g[0] -= count
    elif count > 0:
        o[direction].append(count)

    for d in range(2):
        l = o[d]
        M = sum(l)
        M2 = M * 2
        if abs(g[d]) > M:
            print('No')
            return
        pre = [False] * (M2 + 1)
        pre[M] = True
        for i, v in enumerate(l):
            dp = [False] * (M2 + 1)
            for a in range(M2 + 1):
                if pre[a] == False: continue
                if a >= v:
                    dp[a - v] = True
                if a + v <= M2:
                    dp[a + v] = True
            pre = dp
        if pre[g[d] + M] == False:
            print('No')
            return
    print('Yes')

if __name__ == '__main__':
    input = sys.stdin.readline
    s = input().rstrip()
    x, y = map(int, input().split())
    main(s, x, y)
a, b = input().split()
if a * b % 2 == 0:
    print("True")
else:
    print("False")

### FIXED CODE ###

a, b = map(int, input().split())
 
if a * b % 2 == 0:
  print("Even")
else:
  print("Odd")
n,a,b=map(int,input().split())
print(n//(a+b)*a+min(a,n//%(a+b)))

### FIXED CODE ###

n,a,b=map(int,input().split())
print(n//(a+b)*a+min(a,n%(a+b)))
import math

def nCm(n, m):
    return fact(n) // (fact(m) * (fact(n - m)))


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

saw = [-1] * n
left = 0
right = 0
for i in range(n):
    if saw[a[i] - 1] == -1:
        saw[a[i] - 1] = i
    else:
        left, right = saw[a[i] -1], n - i
        break
print(left, right)

for i in range(1, n+2):
    if i == 1:
        print(n)
    else:
        print((nCm(n+1, i) - nCm(left+right, i - 1) % 1000000007))


### FIXED CODE ###

def power(x, n):
    y = 1
    while n > 0:
        if n % 2 == 0:
            x = (x * x) % (10 ** 9 + 7)
            n = n // 2
        else:
            y = (y * x) % (10 ** 9 + 7)
            n = n - 1
    return y


MOD = 10 ** 9 + 7

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

fact = [1] * (n + 2)
inv = [1] * (n + 3)

for i in range(1, n + 2):
    fact[i] = (i * fact[i - 1]) % MOD
    inv[i] = power(fact[i], MOD - 2) % MOD


def nCm(n, m):
    global fact
    global inv
    return fact[n] * inv[m] % MOD * inv[n - m] % MOD


saw = [-1] * n
left = 0
right = 0
for i in range(n):
    if saw[a[i] - 1] == -1:
        saw[a[i] - 1] = i
    else:
        left, right = saw[a[i] - 1], n - i
        break

for i in range(1, n + 2):
    if i == 1:
        print(n)
    elif left + right >= i - 1:
        print((nCm(n + 1, i) - nCm(left + right, i - 1)) % MOD)
    else:
        print(nCm(n + 1, i))
d={}
for _ in[0]*int(input()):
 a,v=map(int,input().split())
 d[a]=v
m=max(d.items(),key=lambda x:x[1])
print(min(d[m]),m)


### FIXED CODE ###

d={}
for _ in[0]*int(input()):
 a,v=map(int,input().split())
 d[v]=d[v]if v in d and a>d[v]else a
m=max(d)
print(d[m],m)
a,b = map(int,input())

s = a*b
l = 2*a + 2*b
print(s,l)




### FIXED CODE ###

a,b = map(int,input().split())
s = a * b
l = 2*a + 2*b

print(s,l)
n,x=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
c=0
for i in range(len(a)+1):
  if x>0:
    x-=a[i]
    c+=1
  else:
    print(c)
    break

### FIXED CODE ###

n,x=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
c=0
for i in range(n):
  if n>=i and x>=a[i]:
    x-=a[i]
    c+=1
    if n==c and x==0:
      print(n)
    if n==c and x!=0:
      print(n-1)
  else:
    print(c)
    break
n, m = map(int, input().split())

tsuro = [list(map(int, input().split())) for _ in range(m)]

ikeru = [set() for _ in range(n+1)]

for i,j in tsuro:
    ikeru[i].add(j)
    ikeru[j].add(i)

ans = [0]*(n+1)
visited = [n+5]*(n+1)

def dfs(mae,heya,kaiso):
    if visited[heya] <= kaiso:
        return True
    else:
        visited[heya] = kaiso
        ans[heya] = mae
        for j in ikeru[heya]:
            dfs(heya, j, kaiso+1)
        return True

hantei = True
dfs(0,1,0)
for i in range(1, n+1):
    if visited[i] == n+5:
        hantei = False
if hantei:
    print('Yes')
    for j in range(2,n+1):
        print(ans[j])
else:
    print('No')


### FIXED CODE ###

from collections import deque

n, m = map(int,input().split())
graph =[[] for _ in range(n+1)]
for _ in range(m):
    a,b =map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
queue = deque([1])
visited = [False] * (n+1)
visited[0] = True
ans = [0] * (n+1)
while queue:
    node = queue.popleft()
    for xnode in graph[node]:
        if visited[xnode]:
            continue
        ans[xnode]=node
        visited[xnode]=True
        queue.append(xnode)
print("Yes")
for a in ans[2:]:
    print(a)
import numpy as np
words = lambda t : list(map(t, input().split()))



def search(i, visited, ns, ans) :
    #print(i+1)
    visited[i] = True
    for next, weight in ns[i]:
        if visited[next] == False:
            if weight % 2 == 0:
                ans[next] = ans[i]
            else:
                ans[next] = (ans[i]+1) % 2
            search(next, visited, ns, ans)


def dfs(ns, ans):
    visited = [False] * len(ns)
    search(0, visited, ns, ans)

def main():
    n = int(input())
    ns = [[] for _ in range(n)]
    for _ in range(n-1):
        (st,end,weight) = map(int,input().split())
        ns[st-1].append((end - 1,weight))
        ns[end-1].append((st-1,weight))
    ans = [0] * n
    dfs(ns, ans)
    for a in ans:
        print(a)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import numpy as np
words = lambda t : list(map(t, input().split()))

n,k = words(int)
str = input()

c = str[k-1]
ans = str[:k-1] + c.lower() + str[k:]
print(ans)
n, g = map(int, input().split())
List = [list(map(int, input().split())) for i in range(n)]

pre_ans = 0
ans = 0
a = 0
res = 0
x = 0

max_score = [(i+1)*100*List[i][0]+List[i][1] for i in range(n-1, -1, -1)] #全て答えたときのスコアを算出(逆順)
score = [(i+1)*100 for i in range(n-1, -1, -1)] #各レベルの点数を算出しておく(逆順)
howmany = [List[i][0] for i in range(n-1, -1, -1)] #回数も逆順に出しておく

while(ans <= g):
    pre_ans = ans
    ans += max_score[a]
    a += 1
    
for i in range(a):
    res += howmany[i]
    
rest = g - ans
#x = -(-rest // score[a])
if rest > 0:
    x = rest // score[a]

#print(max_score)
#print(score)
#print(howmany)
#print(res)
#print(x)
print(res + x)

### FIXED CODE ###

n, g = map(int, input().split())
List = [list(map(int, input().split())) for i in range(n)]

ans = []

max_score = [(i+1)*100*List[i][0]+List[i][1] for i in range(n-1, -1, -1)] #全て答えたときのスコアを算出(逆順)
score = [(i+1)*100 for i in range(n-1, -1, -1)] #各レベルの点数を算出しておく(逆順)
howmany = [List[i][0] for i in range(n-1, -1, -1)] #回数も逆順に出しておく

for i in range(2**n):
    s = 0
    m = 0
    max = 0 #残りの中で最も得点の単位が大きいもの
    for j in range(n):
        if((i >> j) & 1):
            max += 1
            s += max_score[j]
            m += howmany[j]
    if(s >= g):
        ans.append(m)
    else:
        if(max < n):
            rest = g - s
            k = -(-rest // score[max]) #最も得点の単位の高い問題を何問解くか
            if(k < howmany[max]):
                m += k
                ans.append(m)

print(min(ans))
a,b = [int(input()) for _ in range(2)]
if a*b %2 == 0:
  print("Even")
else:
  print("Odd")

### FIXED CODE ###

a,b = list(map(int,input().split()))
if a*b %2 == 0:
  print("Even")
else:
  print("Odd")
h,w=map(int,input().split())
d='.'*(w+2)
a=[d]
for _ in range(h):
  s='.'+input()+'.'
  a.append(s)
a.append(d)
x='Possible'
a[h][w+1]='#'
for i in range(1,w+1):
  for j in range(1,h+1):
    if a[j][i]=='#':
      if a[j][i+1]==a[j+1][i]:
        x='Impossible'
        break
print(x)

### FIXED CODE ###

h,w=map(int,input().split())
a=[list(input()+'.') for _ in range(h)]
d=['.']*(w+1)
a.append(d)
x=1
i=0;j=0
a[0][0]='.'
while i!=h-1 or j!=w-1:
  if a[i+1][j]=='#':
    if a[i][j+1]=='#':
      x=0
      break
    else:
      i=i+1
      a[i][j]='.'
  else:
    if a[i][j+1]=='.':
      x=0
      break
    else:
      j=j+1
      a[i][j]='.'
if x==1:
  for k in range(h):
    if '#' in a[k]:
      x=0
      break
print('Possible' if x==1 else 'Impossible')
#ABC135A - Harmony
import math
A, B = list(map(int,input().split()))
if math.abs(A-B) % 2 == 1:
    print("IMPOSSIBLE")
else:
    print((A+B)//2)

### FIXED CODE ###

#ABC135A - Harmony
A, B = list(map(int,input().split()))
if (max(A,B) - min(A,B)) % 2 == 1:
    print("IMPOSSIBLE")
else:
    print((A+B)//2)
from math import pi
a=int(input())
print(a*pi)


### FIXED CODE ###

from math import pi
a=float(input())
print(a*a*pi, 2*a*pi)
N,K = map(int,input().split())
enemys = list(map(int,input().split()))
enemys = sorted(enemys,reversed = True)
if K >= len(enemys):
  print(0)
else:
  enemys = enemys[K+1:]
  print(sum(enemys))

### FIXED CODE ###

N,K = map(int,input().split())
enemys = list(map(int,input().split()))
enemys = sorted(enemys,reverse = True)
if K >= N:
  print(0)
elif K == 0:
  print(sum(enemys))
else:  
  enemys = enemys[K:]
  print(sum(enemys))
a,b=map(int,input().split(''))
m=a*b
if m%2=1:
  return 'Odd'
else:
  return 'Even'

### FIXED CODE ###

a,b=map(int,input().split())
m=a*b
if m%2==1:
  print('Odd')
else:
  print('Even')
elements = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]

if K < 16:
    print(elements[K-1])
else:
    print(elements[-(32-K)-1])


### FIXED CODE ###

elements = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
K = int(input())
th = K-1
print(elements[th])
S = input()
K = int(input())
if len(S) > K and S[:K].count(1) == K:
    print(1)
else:
    for c in S:
        if c != '1':
            print(c)
            break


### FIXED CODE ###

S = input()
K = int(input())
if len(S) >= K and S[:K].count("1") == K:
    print(1)
else:
    for c in S:
        if c != "1":
            print(c)
            break