Harryxun/stf_run huggingface dataset:
from collections import Counter

def update(dic, b, c):
    n = dic.pop(b)
    dic[c] = n + dic.get(c, 0)
    
def calc_diff(dic, b, c):
    return c * dic[b] - b * dic[b]

def calc_total(dic):
    return sum(k * v for k, v in dic.items())

N = int(input())
lis = list(map(int, input().split()))
dic = dict(Counter(lis))
Q = int(input())
total = calc_total(dic)
for _ in range(Q):
    B, C = map(int, input().split())
    total += calc_diff(dic, B, C)
    print(total)
    update(dic, B, C)

### FIXED CODE ###

from collections import Counter

def update(dic, b, c):
    n = dic.pop(b)
    dic[c] = n + dic.get(c, 0)
    
def calc_diff(dic, b, c):
    if dic.get(b):
        return c * dic[b] - b * dic[b]
    return 0

def calc_total(dic):
    return sum(k * v for k, v in dic.items())

N = int(input())
lis = list(map(int, input().split()))
dic = dict(Counter(lis))
Q = int(input())
total = calc_total(dic)
for _ in range(Q):
    B, C = map(int, input().split())
    diff = calc_diff(dic, B, C)
    total += diff
    print(total)
    if diff:
        update(dic, B, C)
X = int(input())

import math
def is_beki(n):
  for i in range(2, int(math.sqrt(n)//1)+1):
    beki = i
    while beki <= n:
      if beki == n:
        return True
      beki = beki * i
  return False

for i in range(X, 1, -1):
  if is_beki(i):
    break
print(i)

### FIXED CODE ###

X = int(input())

import math
def is_beki(n):
  for i in range(2, int(math.sqrt(n)//1)+1):
    beki = i
    while beki <= n:
      if beki == n:
        return True
      beki = beki * i
  return False

if X == 1:
  print(1)
else:
  for i in range(X, 1, -1):
    if is_beki(i):
      break
  print(i)
N, M = map(int, input().split())
G = [[] for i in range(N + 1)]
for i in range(M):
    l, r, d = map(int, input().split())
    l, r = l - 1, r - 1
    G[l].append((r, d))
    G[r].append((l, -d))
used = [False] * (N + 1)
dist = [0] * (N + 1)
flag = False


def dfs(v, d0):
    global flag
    if used[v]:
        if dist[v] != d0:
            flag = True
        return
    else:
        used[v] = True
        dist[v] = d0

    for w, d1 in G[v]:
        dfs(w, d0 + d1)


for i in range(1, N + 1):
    if not used[i]:
        dfs(i, 0)

if flag:
    print("No")
else:
    print("Yes")

### FIXED CODE ###

import sys
sys.setrecursionlimit(200002)
N, M = map(int, input().split())
G = [[] for i in range(N)]
for i in range(M):
    l, r, q = map(int, input().split())
    G[l - 1].append((r - 1, q))
    G[r - 1].append((l - 1, -q))
X = [None] * N


def dfs(u):
    global X, G
    for w, d in G[u]:
        if X[w] is None:
            X[w] = X[u] + d
            if not dfs(w):
                return False
        else:
            if X[w] != X[u] + d:
                return False

    return True


flag = True
for i in range(N):
    if X[i] is None:
        X[i] = 0
        flag &= dfs(i)

if flag:
    print("Yes")
else:
    print("No")
count = input()
numbers = map(int, input().split(' '))

counter = 0
while True:
  tmp = 0
  for item in numbers:
    tmp += item % 2
  if tmp > 0:
    break
  counter ++
  numbers = [item / 2 for item in numbers]
print(counter)

### FIXED CODE ###

count = int(input())
numbers = [int(num) for num in input().split()]

counter = 0
while True:
  tmp = 0
  for item in numbers:
    tmp += item % 2
  if tmp > 0:
    break
  counter += 1
  numbers = [item / 2 for item in numbers]
print(counter)
A,B,K=map(int,input().split())
if A>=K:
  print(str(A-K)+" "+str(B))
else:
  t=K-A
 
  print("0"+" "+str(max(B-t,"0")))
A,B,K=map(int,input().split())
if A>=K:
  print(str(A-K)+" "+str(B))
else:
  t=K-A
 
  print("0"+" "+str(max(B-t,"0")))

### FIXED CODE ###

N,M,K=map(int,input().split())

if N<K:
  M=M-(K-N)
  N=0
else:
  N=N-K

if M<0:
  M=0
print(N,M)
def main():
	n  = int(input())
	arr = []
	for _ in range(n):
		arr.append(int(input()))
	arr2 = arr.copy()
	arr2.sort()
	mx = arr2[-1]
	mx2 = arr2[-2]
	for i in range(len(arr)):
		if arr[i]==mx:
			print(mx2)
		else:
			print(mx)

main()


### FIXED CODE ###

def main():
	n  = int(input())
	arr = []
	for _ in range(n):
		arr.append(int(input()))
	arr2 = arr.copy()
	arr2.sort()
	mx = arr2[-1]
	mx2 = arr2[-2]
	for i in range(len(arr)):
		if arr[i]==mx:
			print(mx2)
		else:
			print(mx)

main()
# ABC104A - Rated for Me
r = list(map(int, input().rstrip().split()))
if r < 1200:
    print("ABC")
elif 1200 <= r < 2800:
    print("ARC")
else:
    print("AGC")

### FIXED CODE ###

# ABC104A - Rated for Me
r = int(input())
if r < 1200:
    print("ABC")
elif 1200 <= r < 2800:
    print("ARC")
else:
    print("AGC")
k=input().split(" ")[0]
a = list(map(lambda x: int(x), input().split("\n")[1].split(" ")))
df = max(a) - min(a)
print(min(df, k - df))

### FIXED CODE ###

k=int(input().split(" ")[0])
a = sorted(map(lambda x: int(x), input().split("\n")[0].split(" ")))
dfs=[k-a[len(a)-1]+a[0]]
for i in range(len(a) - 1):
    dfs.append(a[i+1]-a[i])
print(sum(dfs)-max(dfs))
from heapq import heappop
from heapq import heappush
from heapq import heappushpop


FIN=10**10
N,K=map(int,input().split())

a=[list(map(int,input().split()))[::-1] for i in range(N) ]
a.sort(reverse=True)

l=[]
dic1={}
dic2={}

for i in range(K):
    p=a[i][1]
    if p in dic1:
        if a[i][0]>dic2[p]:
            heappush(l,dic2[p])
            dic2[p]=a[i][0]
        else: heappush(l,a[i][0])

    else: 
        dic1[p]=1
        dic2[p]=a[i][0]


s=sum(l)+sum(dic2.values())
x=len(dic1)
ans=s+x**2

for i in range(K,N):
    if not a[i][1] in dic1:
        dic1[a[i][1]]=1
        s+=a[i][0]-heappop(l)
        x+=1
        ans=max(ans,s+x**2) 

    if l==[]: break

print(ans)
        

### FIXED CODE ###

from heapq import heappop
from heapq import heappush
from heapq import heappushpop

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

a=[list(map(int,input().split()))[::-1] for i in range(N) ]
a.sort(reverse=True)

l=[]
dic1={}
dic2={}

for i in range(K):
    [d,t]=a[i]
    if t in dic1:
        if d>dic2[t]:
            heappush(l,dic2[t])
            dic2[t]=d
        else: heappush(l,d)

    else: 
        dic1[t]=1
        dic2[t]=d


s=sum(l)+sum(dic2.values())
x=len(dic1)
ans=s+x**2

for i in range(K,N):
    if l==[]: break
        
    [d,t]=a[i]
    if not t in dic1:
        dic1[t]=1
        s+=d-heappop(l)
        x+=1
        ans=max(ans,s+x**2) 

    

print(ans)
W, H, x, y = (int(i) for i in input().split())
if x=W/2 and y=H/2:
  print(W*H/2, 0)
else:
  print(W*H/2, 1)

### FIXED CODE ###

W, H, x, y = (int(i) for i in input().split())
if x==W/2 and y==H/2:
  print(W*H/2, 1)
else:
  print(W*H/2, 0)
_,T,*a=map(int,open(0).read().split())
print(sum([min(i-j,t) for i,j in zip(a,[0]+a)]))

### FIXED CODE ###

n,T=map(int,input().split())
t=[int(i) for i in input().split()]
ans=0
pre=t[0]
for i in range(1,n):
    c=t[i]
    if c-pre>T:
        ans+=T
    else:
        ans+=c-pre
    pre=c
print(ans+T)
N, K = [int(x) for x in input().split(' ')]
m = 10**9 + 7
import math
def combination(n, r):
  return math.factorial(n) // (math.factorial(n-r) * math.factorial(r))
  
for k in range(1, K+1):
  print(combination(N-K+1, k) * combination(K-1, k-1) % m)


### FIXED CODE ###

N, K = [int(x) for x in input().split(' ')]
m = 10**9 + 7
fact = [1] * (N+1)
for i in range(1, N+1):
  fact[i] = fact[i-1] * i
  
def combination(n, r):
  return fact[n] // fact[r] // fact[n-r]
  
for k in range(1, K+1):
  print(combination(N-K+1, k) % m * combination(K-1, k-1) % m)
# どうやって自明な条件で計算量を落としていくか
# 不等式に注目。pythonが耐えるのは10^6程度
import numpy as np
X,Y,Z,K = map(int,input().split())
As = sorted(list(map(int,input().split())),reverse=True)
Bs = sorted(list(map(int,input().split())),reverse=True)
Cs = sorted(list(map(int,input().split())),reverse=True)

# ABでソート
AB = []
for A in As:
    for B in Bs:
        AB.append(A+B)
ABs = sorted(AB,reverse=True)

# その中からK番目まで
ABC = []
for i in range(min(len(AB),K)):
    for C in Cs:
        ABC.append(AB[i]+C)

ABCs = sorted(ABC,reverse=True)
for i in range(K):
    print(ABCs[i])

### FIXED CODE ###

# どうやって自明な条件で計算量を落としていくか
# 不等式に注目。pythonが耐えるのは10^6程度
X,Y,Z,K = map(int,input().split())
As = sorted(list(map(int,input().split())),reverse=True)
Bs = sorted(list(map(int,input().split())),reverse=True)
Cs = sorted(list(map(int,input().split())),reverse=True)

# ABでソート
AB = []
for A in As:
    for B in Bs:
        AB.append(A+B)
ABs = sorted(AB,reverse=True)

# その中からK番目まで
ABC = []
for i in range(min(len(ABs),K)):
    for C in Cs:
        ABC.append(ABs[i]+C)

ABCs = sorted(ABC,reverse=True)
for i in range(K):
    print(ABCs[i])
A, B = [int(x) for x i input().split()]
if (A*B) % 2 == 0:
  print('Even')
else:
  print('Odd')

### FIXED CODE ###

A, B = [int(x) for x in input().split()]

if (A*B) % 2 == 0:
    print('Even')
else:
    print('Odd')
from functools import lru_cache
N, A = map(int, input().split())
X = [int(x) for x in input().split()]

@lru_cache(1000000000, False)
def solve(i, n, s):
    if s < 0:
        return -1
    if N-i+1 < n:
        return -1
    if n == 0:
        if s == 0:
            return 1
        else:
            return -1
    if i == N:
        return -1
    s1 = solve(i+1, n-1,s-X[i])
    s2 = solve(i+1, n, s)
    if s1 == -1 and s2 == -1:
        return -1
    if s1 == -1:
        return s2
    if s2 == -1:
        return s1
    return s1 + s2


answer = 0
for n in range(1, N+1):
    s = solve(0, n, n*A)
    if s != -1:
        #print(n, s)
        answer += s
print(answer)

def test():
    import itertools
    for a in itertools.combinations(X,3):
        if sum(a) == A*3:
            print(a)

### FIXED CODE ###

N, A = map(int, input().split())
X = sorted([int(x) for x in input().split()])
from collections import defaultdict , Counter
dp = defaultdict(Counter)

dp[0] = Counter({0:1})

for i in range(1, N+1):
    x = X[i-1]
    k = 0
    update = []
    for s, counter in list(dp.items()):
        for nCard, count in counter.items():
            update.append((s+x, nCard+1, count))

    for key, value, diff in update:
        dp[key][value] += diff

def printCounter(counter):
    if len(counter) == 0:
        return ""
    return dict(counter)
if False:
    for s in range(0, max(X)*N):
        print("%2d" % s, "|", printCounter(dp[s]))

answer = 0
for s, counter in dp.items():
    q, r = divmod(s, A)
    if r != 0:
        continue
    answer += counter[q]
print(answer-1)
import bisect
n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
bc=[]
for i in range(m):
    b,c=map(int,input().split())
    bc.append([b,c])
bc.sort(key=lambda x:x[1],reverse=True)
x=[0]*(m+3)
for i in range(m):
    x[i+1]=min(bisect.bisect_left(a,bc[i][1]), bc[i][0])+x[i]
    for j in range(x[i],x[i+1]+1):
        a[j]=bc[i][1]


print(sum(a))


### FIXED CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
l=[]
for i in range(n):
    l.append([1,a[i]])
for i in range(m):
    l.append(list(map(int,input().split())))
l.sort(key=lambda x:x[1], reverse=True)
c=0
ans=0
for i in range(n+m):
    ans+=l[i][1]*l[i][0]
    c+=l[i][0]
    if c>n:
        ans-=l[i][1]*(c-n)
        break
print(ans)
n= input()
s = input()
G = groupby(s)

print(len(list(G)))

### FIXED CODE ###

from itertools import groupby
n= input()
s = input()
G = groupby(s)

print(len(list(G)))
req = int(input())
count = 0
while P < req:
  p += int(P/100)
  count +=1
  
print(count)

### FIXED CODE ###

req = int(input())
count = 0
p = 100
while p < req:
  p = p * 101//100
  p = int(p)
  count +=1
  
print(count)
!/usr/bin/env python3

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

if n == 1:
    print(1)
    exit(0)
if n == 2:
    if abs(a[0]-a[1]) <= 2:
        print(2)
    else:
        print(1)
    exit(0)

if n >= 3:
    d = [0 for _ in range(100001)]
    for i in range(n):
        d[a[i]] += 1
    ans = 0 
    for i in range(n-2):
        tmp = d[i] + d[i+1] + d[i+2]
        if ans <= tmp:
            ans = tmp 

print(ans)


### FIXED CODE ###

#!/usr/bin/env python3

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

if n == 1:
    print(1)
    exit(0)
if n == 2:
    if abs(a[0]-a[1]) <= 2:
        print(2)
    else:
        print(1)
    exit(0)

if n >= 3:
    d = [0 for _ in range(100001)]
    for i in range(n):
        d[a[i]] += 1
    ans = 0 
    for i in range(100001-2):
        tmp = d[i] + d[i+1] + d[i+2]
        if ans <= tmp:
            ans = tmp 

print(ans)
N=int(input())
a=list(map(int,input().split()))
m=max(a)
c=[0]*(m+1)

for i in a:
    c[i]=c[i]+1
T=c[0]+c[1]+c[2]
for i in range(m):
    T=max(T,c[i-1]+c[i]+c[i+1])
print(T)

### FIXED CODE ###

N=int(input())
a=list(map(int,input().split()))
m=max(a)
c=[0]*(m+3)

for i in a:
    c[i]=c[i]+1

if len(c)==1:
    T=1
else:
    T=c[0]+c[1]+c[2]
    for i in range(m):
        T=max(T,c[i-1]+c[i]+c[i+1])
print(T)
if __name__ == '__main__':
    N = int(input())
    C = list(input())
    cnt = 0
    red_cnt = 0
    for c in C:
        if c == 'R':
            red_cnt += 1

    for i in range(red_cnt+1):
        if C[i] == 'W':
            for j in range(red_cnt, N):
                if C[j] == 'R':
                    C[i] = 'R'
                    C[j] = 'W'
                    cnt += 1
                    red_cnt = j+1
    print(cnt)

### FIXED CODE ###

if __name__ == '__main__':
    N = int(input())
    C = list(input())
    cnt = 0
    red_cnt = 0
    for c in C:
        if c == 'R':
            red_cnt += 1

    for i in range(red_cnt):
        if C[i] == 'W':
            for j in range(red_cnt, N):
                if C[j] == 'R':
                    C[i] = 'R'
                    C[j] = 'W'
                    cnt += 1
                    red_cnt = j+1
    print(cnt)
ef main():
    a1, a2, a3 = map(int, input().split())
    if (a1+a2+a3) <= 21:
        print("win")
    else:
        print("bust")

if __name__ == "__main__":
    main()

### FIXED CODE ###

a, b, c = (int(i) for i in input().split())
if a + b + c <= 21:
  print("win")
else:
  print("bust")
import math

n, m = map(int, input().split())
A = list(map(int, input().split()))
As = sorted(A, reverse = True)
for i in range(m):
    ii = math.floor(As[0]/2)
    As[0] = ii
    if As[0] < As[1]:
        As = sorted(As, reverse=True)


print(int(sum(As)))


### FIXED CODE ###

import math
import heapq

n, m = map(int, input().split())
A = list(map(int, input().split()))
A = list(map(lambda x:x*(-1), A))
heapq.heapify(A)
for i in range(m):
    min = (-1)*((-1)*(heapq.heappop(A))//2)
    heapq.heappush(A, min)


print(int(sum(A))*(-1))
N=int(input())
K=int(input())
import math
x=math.floor(math.log10(N))+1
def combinations_count(n, r):
  return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
ans=0
if x<K:
  print(0)
  exit(0)
if K==1:
  ans=(x-1)*9
  ans+=(N//10**(x-1))
  print(ans)
elif K==2:
  for i in range(2,x):
    ans+=(9**2)*(i-1)
  f=(N//10**(x-1))
  n=str(N)
  for i in range(1,x):
    if n[i]!='0':
      s_n=x-i
      s=int(n[i])
      break
  ans+=(f-1)*9*(x-1)
  ans+=9*(s_n-1)
  ans+=s
  print(ans)
else:
  for i in range(3,x):
    ans+=(9**3)*combinations_count(i-1,2)
  f=(N//10**(x-1))
  n=str(N)
  s_n=0
  t_n=0
  for i in range(1,x):
    if n[i]!='0':
      s_n=x-i
      s=int(n[i])
      break
  for i in range(x-s_n+1,x):
    if n[i]!='0':
      t_n=x-i
      t=int(n[i])
      break
  if s_n==2:
    ans+=(f-1)*9**2*combinations_count(x-1,2)
    ans+=(s-1)*9*(s_n-1)
    if t_n!=0:
      ans+=9*(t_n-1)
    ans+=t
  else:
    ans+=(f-1)*9**2*combinations_count(x-1,2)
    ans+=9**2*combinations_count(s_n-1,2)
    ans+=(s-1)*9*(s_n-1)
    if t_n!=0:
	    ans+=9*(t_n-1)
    ans+=t
  print(ans)

### FIXED CODE ###

Nstr=input()
N=int(Nstr)
K=int(input())
x=len(Nstr)
dp0=[[0]*(K+1) for i in range(x+1)]
dp1=[[0]*(K+1) for i in range(x+1)]

dp1[0][0]=1

for i in range(1,x+1):
  dp0[i][0]=dp0[i-1][0]+dp1[i-1][0]
  for j in range(1,K+1):
    if Nstr[i-1]!='0':
      dp1[i][j]=dp1[i-1][j-1]
      dp0[i][j]+=(dp1[i-1][j-1]*(int(Nstr[i-1])-1)+dp1[i-1][j])
    else:
      dp1[i][j]=dp1[i-1][j]
    dp0[i][j]+=(dp0[i-1][j]+dp0[i-1][j-1]*9)

    
  '''  
  if Nstr[i-1]!='0':
    for j in range(1,K+1):
      dp1[i][j]=dp1[i-1][j-1]
      dp0[i][j]+=(dp1[i-1][j-1]*(int(Nstr[i-1])-1)+dp1[i-1][j])
  else:
    for j in range(1,K+1):
      dp1[i][j]=dp1[i-1][j]
  for j in range(1,K+1):
    dp0[i][j]+=(dp0[i-1][j]+dp0[i-1][j-1]*9)
  '''
print(dp0[x][K]+dp1[x][K])
from collections import deque
s = deque(input())
num = int(input())
for i in range(num):
  a = deque(input().split())
  start = int(a[0])
  if start == 2:
    ns = int(a[1])
    if ns == 1:
      s.appendleft(a[2])
      #s = a[2] + s
    else:
      #s = s + a[2]
      s.append(a[2])
  else:
    s = s[::-1]
for i in range(len(s)):
  print(s[i], end='')

### FIXED CODE ###

from collections import deque
s = deque(input())
num = int(input())
cnt = 0
for i in range(num):
  a = input().split()

  if a[0] == '2':
    if (int(a[1])+cnt)%2==1:
      s.appendleft(a[2])
    else:
      s.append(a[2])
  else:
    cnt += 1
if cnt%2 == 1:    
	s.reverse()
print("".join(s))
h,w=map(int,input().split())
l=[list(map(input().split())) for i in range(h)]

row=[False]*h
col=[False]*w

for i in range(h):
  for j in range(w):
    if a[i][j]=="#":
      row[i]="True"
      col[j]="True"

for i in range(h):
  if row[i]:
    for j in range(w):
      if col[j]:
        print(a[i][j], end="")
    print()

### FIXED CODE ###

H, W = map(int, input().split())
a = []
for _ in range(H):
    i = list(input())
    if '#' in i:
        a.append(i)
ans = zip(*[i for i in zip(*a) if '#' in i])
for s in ans:
    print(*s, sep='')
ok = [[0,4,8], [2,4,6], [0,1,2], [3,4,5], [6,7,8], [0,3,6], [1,4,7], [2,5,8]]
while True:
    s = input()
    if len(s) == 0:
        break
    maru = []
    batu = []
    for i in range(9):
        if s[i] == 'o':
            maru.append(i)
        elif s[i] == 'x':
            batu.append(i)
    print(maru, batu)
    flag = False
    for i in ok:
        if i == maru:
            print("o")
            flag = True
            break
        elif i ==batu:
            print("x")
            flag = True
            break
    if not flag:
        print("d")

### FIXED CODE ###

ok = [[0,4,8], [2,4,6], [0,1,2], [3,4,5], [6,7,8], [0,3,6], [1,4,7], [2,5,8]]
while True:
    try:
        s = input()
    except EOFError:
        break
    flag = False
    for i in ok:
        if s[i[0]] == s[i[1]] == s[i[2]] and s[i[0]] != 's':
            print(s[i[0]])
            flag = True
            break
    if flag:
        continue
    print("d")
s=input()
if s=='RRR':
  print(3)
elif s=='SSS':
  print(0)
elif (s=='SRR' or s=='RRS'):
  prinr(2)
else:
  print(1)

### FIXED CODE ###

s=input()
if s=='RRR':
  print(3)
elif s=='SSS':
  print(0)
elif (s=='SRR' or s=='RRS'):
  print(2)
else:
  print(1)
W, H, N = list(map(int, input().split()))

min_x = 0
min_y = 0
max_x = W
max_y = H

for i in range(N):
    x, y, a = list(map(int, input().split()))
    if a == 1:
        min_x = max(min_x, min(max_x, x))
    if a == 2:
        max_x = min(max_x, max(min_x, x))
    if a == 3:
        min_y = max(min_y, min(max_y, y))
    if a == 4:
        max_y = min(max_y, max(min_y, y))

print((max_x - min_x) * (max_y - min_y))


### FIXED CODE ###

L = list(map(int, input().split()))
max_index = L.index(max(L))

X = 0
S = 0

for i in range(3):
    if i == max_index:
        X = L[i]
    else:
        S += L[i]

if X == S:
    print("Yes")
else:
    print("No")
import collections

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

s = len(set(v))
if s == 1:
    print(n // 2)
    exit()

odd = v[::2]
even = v[1::2]
mo = collections.Counter(odd).most_common()[0]
mo2 = collections.Counter(odd).most_common()[1]
me = collections.Counter(even).most_common()[0]
me2 = collections.Counter(even).most_common()[1]

if mo[0] == me[0]:
    if me2[1] < mo2[1]:
        mo = mo2
    else:
        me = me2
print(abs((n // 2) - mo[1]) + abs((n // 2) - me[1]))


### FIXED CODE ###

import collections

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

s = len(set(v))
if s == 1:
    print(n // 2)
    exit()

odd = v[::2]
even = v[1::2]
mo = collections.Counter(odd).most_common(2)
me = collections.Counter(even).most_common(2)

if mo[0][0] != me[0][0]:
    print(n - mo[0][1] - me[0][1])
elif len(mo) == 1:
    print(n - mo[0][1] - me[1][1])
elif len(me) == 1:
    print(n - mo[1][1] - me[0][1])
else:
    print(n - max(mo[0][1] + me[1][1], mo[1][1] + me[0][1]))
main():
    S = input()
    K = int(input())
    output = solve(S, K)
    return output

def solve(S, K):
    for s in S:
        if s != "1":
            return s
    return "1"

### FIXED CODE ###

def main():
    S = input()
    K = int(input())
    output = solve(S, K)
    print(output)
    return

def solve(S, K):
    if K <= len(S) and S[:K] == "1"*K:
        # 文字列の1番目からK番目までがすべて1だった場合、
        # それ以降の文字列に1以外の数字があっても1が答え
        return "1"
    for s in S:
        if not s == "1":
            return s  # Sの"1"ではない、最初の数字が答え
if __name__ == "__main__":
    main()
N=int(input())
v=[[] for i in range(N)]
r=list()

def wps(s,d,u):
  c=1
  for i in range(len(v[d])):
    if v[d][i][0]!=s:
      c=c if u!=c else c+1
      v[d][i][1]=c
      wps(d,v[d][i][0],c)
      c+=1
    else:
      v[d][i][1]=u


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

wps(-1,0,-1)

m=0
for i in range(N):
  for j in range(len(v[i])):
    if i<v[i][j][0]:
      r.append(v[i][j])
  m=max(m,len(v[i]))

print(m)
r.sort(key=lambda x:x[2])
for e in r:
	print(e[1])


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**5)

N=int(input())
v=[[] for i in range(N)]
r=list()

def wps(s,d,u):
  c=1
  for i in range(len(v[d])):
    if v[d][i][0]!=s:
      c=c if u!=c else c+1
      v[d][i][1]=c
      wps(d,v[d][i][0],c)
      c+=1
    else:
      v[d][i][1]=u


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

wps(-1,0,-1)

m=0
for i in range(N):
  for j in range(len(v[i])):
    if i<v[i][j][0]:
      r.append(v[i][j])
  m=max(m,len(v[i]))

print(m)
r.sort(key=lambda x:x[2])
for e in r:
	print(e[1])
n=int(raw_input())
p=[0,0]
for i in range(n):
        c=[0 for i in range(100)]
        c=map(list,raw_input().split())
        m=0
        while 1:
                if c[0]==c[1]:
                        p[0]+=1
                        p[1]+=1
                        break
                elif c[0][m]<c[1][m]:
                        p[1]+=3
                        break
                elif c[1][m]<c[0][m]:
                        p[0]+=3
                        break
                m+=1
print p[0], p[1]

### FIXED CODE ###

n=int(raw_input())
p=[0,0]
for i in range(n):
        c=[0 for i in range(100)]
        c=map(list,raw_input().split())
        m=0
        while 1:
                try:
                        if c[0]==c[1]:
                                p[0]+=1
                                p[1]+=1
                                break
                        elif c[0][m]<c[1][m]:
                                p[1]+=3
                                break
                        elif c[1][m]<c[0][m]:
                                p[0]+=3
                                break
                        m+=1
                except IndexError:
                        if len(c[0])<len(c[1]):
                                p[1]+=3
                                break
                        if len(c[1])<len(c[0]):
                                p[0]+=3
                                break
print p[0], p[1]
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

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

n, m = map(int, input().split())
s = list(input())
t = list(input())

s1 = ['*'] * lcm(n, m)
l = len(s1)

for i in range(n):
    s1[(l//n) * i] = s[i]

for j in range(m):
    if s1[(l//m) * j] != '*':
        if s1[(l//m) * j] != t[j]:
            print(-1)
            break
    if j == m - 1:
        print(l)

### FIXED CODE ###

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

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

n, m = map(int, input().split())
s = list(input())
t = list(input())

for i in range(gcd(n, m)):
    if s[i * (n // gcd(n, m))] != t[i * (m // gcd(n, m))]:
        print(-1)
        break
    if i == gcd(n, m) - 1:
        print(lcm(n, m))