Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
import math
from functools import reduce
n = int(input())
a = list(map(int, input().split()))

def gcd(*num):
    return reduce(math.gcd, num)

print(gcd(*a))


Fixed submission:
import fractions
from functools import reduce
n = int(input())
a = list(map(int, input().split()))

def gcd(*num):
    return reduce(fractions.gcd, num)

print(gcd(*a))
Buggy python submission (verdict: Runtime Error):
from math import log2
n, k = map(int, input().split())
a = list(map(int, input().split()))
m = max(a)
r = int(log2(m))
rank = [0]*(r+1)
for y in a:
    tmp = y
    for j in range(r, -1, -1):
        if tmp >= 2**j:
            rank[j] += 1
            tmp -= 2**j

y = 0
if k >= 2**(r+1):
    for i in range(int(log2(k)), r, -1):
        if y > k:
            break
        else:
            y += 2**i
    ans1 = ans2 = y
else
    ans1 = ans2 = 0
x1 = 0
for i in range(r, -1, -1):
    if rank[i] <= n//2:
        if x1 + 2**i > k:
            break
        else:
            x1 += 2**i
            ans1 += 2**i*(n-rank[i])
    else:
        ans1 += 2**i*rank[i]

x2 = 0
for i in range(r, -1, -1):
    if rank[i] <= n//2:
        if x2 + 2**i > k:
            break
        else:
            x2 += 2**i
            ans2 += 2**i*(n-rank[i])
    else:
        ans2 += 2**i*rank[i]

ans = max(ans1, ans2)



Fixed submission:
n, k = map(int, input().split())
a = list(map(int, input().split()))
h = [[0, 0] for _ in range(41)]
b = list(map(int, bin(k)[2:].zfill(41)))
for i in a:
    for x, y in enumerate(map(int, bin(i)[2:].zfill(41))):
        h[x][y] += 1

ans = 0
ctr = 0
hm = [max(x, y)*2**(40-i) for i, [x, y] in enumerate(h)]
for i, v in enumerate(b):
    if not v:
        ctr += h[i][1]*2**(40-i)
    else:
        ans = max(ans, ctr+h[i][1]*2**(40-i)+sum(hm[i+1:]))
        ctr += h[i][0]*2**(40-i)
print(max(ans, ctr))
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
N, M = map(int, input().split())
X = list(map(int, input().split()))
EDGE = [list(map(int, input().split())) for i in range(M)]
EDGE.sort(key=lambda x:x[2])

EDGELIST = [[] for i in range(N+1)]
for i in range(M):
    x, y, w = EDGE[i]
    EDGELIST[x].append(i)
    EDGELIST[y].append(i)

Group = [i for i in range(N+1)]

def find(x):
    while Group[x] != x:
        x = Group[x]
    return x

def Union(x, y):
    if find(x) != find(y):
        Group[find(y)] = Group[find(x)] = min(find(y), find(x))

USE = [0]*M
WEIGHTSUM = [0] + [X[i] for i in range(N)]

QUE = deque()

for i in range(M):
    x, y, w = EDGE[i]

    if find(x) != find(y):
        WEIGHTSUM[find(x)] = WEIGHTSUM[find(y)] = WEIGHTSUM[find(x)] + WEIGHTSUM[find(y)]
        Union(x, y)

    if w <= WEIGHTSUM[find(x)]:
        QUE.append(i)

while QUE:
    q = QUE.pop()
    x, y, w = EDGE[q]

    NQUE = deque([q])

    while NQUE:
        nq = NQUE.pop()

        if USE[nq] == 1:
            continue

        x, y, _ = EDGE[nq]
        for e in EDGELIST[x] + EDGELIST[y]:
            if EDGE[e][2] <= w:
                NQUE.append(e)
        USE[nq] = 1

print(USE.count(0))



Fixed submission:
import sys
input = sys.stdin.readline
from collections import deque
N, M = map(int, input().split())
X = list(map(int, input().split()))
EDGE = [list(map(int, input().split())) for i in range(M)]
EDGE.sort(key=lambda x:x[2])

EDGELIST = [[] for i in range(N+1)]
for i in range(M):
    x, y, w = EDGE[i]
    EDGELIST[x].append(i)
    EDGELIST[y].append(i)

Group = [i for i in range(N+1)]

def find(x):
    while Group[x] != x:
        x = Group[x]
    return x

def Union(x, y):
    if find(x) != find(y):
        Group[find(y)] = Group[find(x)] = min(find(y), find(x))

USE = [0]*M
WEIGHTSUM = [0] + [X[i] for i in range(N)]

QUE = deque()

for i in range(M):
    x, y, w = EDGE[i]

    if find(x) != find(y):
        WEIGHTSUM[find(x)] = WEIGHTSUM[find(y)] = WEIGHTSUM[find(x)] + WEIGHTSUM[find(y)]
        Union(x, y)

    if w <= WEIGHTSUM[find(x)]:
        QUE.append(i)

while QUE:
    q = QUE.pop()
    x, y, w = EDGE[q]

    NQUE = deque([q])

    while NQUE:
        nq = NQUE.pop()

        if USE[nq] == 1:
            continue

        x, y, _ = EDGE[nq]
        for e in EDGELIST[x] + EDGELIST[y]:
            if EDGE[e][2] <= w:
                NQUE.append(e)
        USE[nq] = 1

print(USE.count(0))
Buggy python submission (verdict: Runtime Error):
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

if sum(a) < sum(b):
    print(-1)
    exit()

q = []
p = []
d = 0

for i in range(n):
    if a[i] - b[i] < 0:
        q.append(a[i]-b[i])
    elif a[i] - b[i] > 0:
        p.append(a[i]-b[i])
    else:
        d += 1

s = sum(q)
p = sorted(p)
while s < 0:
    if p == []:
        print(-1)
        exit()
    else:
        t = p.pop()
        s += t

print(n - d - len(p))



Fixed submission:
a = set(map(int, input().split()))

if a == {1, 9, 7, 4}:
    print("YES")
else:
    print("NO")
Buggy python submission (verdict: Time Limit Exceeded):
mod = 10**9+7
n, m = map(int, input().split())
a = sorted(list(map(int, input().split())), reverse=True)
b = sorted(list(map(int, input().split())), reverse=True)

if len(a) != len(set(a)) or len(b) != len(set(b)):
    print(0)
    exit()

c = 1
N = 0
M = 0
for k in range(n*m, 0, -1):
    if k in a and k in b:
        N += 1
        M += 1
    elif k in a:
        c *= M
        N += 1
    elif k in b:
        c *= N
        M += 1
    else:
        c *= M*N - (m*n-k)
    c %= mod

print(c)


Fixed submission:
mod = 10**9+7
n, m = map(int, input().split())
a = sorted(list(map(int, input().split())), reverse=True)
b = sorted(list(map(int, input().split())), reverse=True)

if len(a) != len(set(a)) or len(b) != len(set(b)):
    print(0)
    exit()

a = set(a)
b = set(b)

c = 1
N = 0
M = 0
for k in range(n*m, 0, -1):
    if k in a and k in b:
        N += 1
        M += 1
    elif k in a:
        c *= M
        N += 1
    elif k in b:
        c *= N
        M += 1
    else:
        c *= M*N - (m*n-k)
    c %= mod

print(c)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
n, k = map(int, input().split())
h = list(map(int, input().split()))
inf = float("inf")
dp = [inf]*n
dp[0] = 0
for i in range(1, n):
    for j in range(1, min(i, k)+1):
        dp[i] = min(dp[i], dp[i-j] + abs(h[i]-h[i-j]))

print(dp[-1])



Fixed submission:
import sys
input = sys.stdin.readline
n, k = map(int, input().split())
h = list(map(int, input().split()))
inf = float("inf")
dp = [inf]*n
dp[0] = 0
for i in range(1, n):
    for j in range(1, min(i, k)+1):
        dp[i] = min(dp[i], dp[i-j] + abs(h[i]-h[i-j]))

print(dp[-1])

Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
h = list(map(int, input().split()))
inf = float("inf")
dp = [inf]*n
dp[0] = 0
for i in range(1, n):
    for j in range(1, min(i, k)+1):
        dp[i] = min(dp[i], dp[i-j] + abs(h[i]-h[i-j]))

print(dp[-1])



Fixed submission:
import sys
input = sys.stdin.readline
n, k = map(int, input().split())
h = list(map(int, input().split()))
inf = float("inf")
dp = [inf]*n
dp[0] = 0
for i in range(1, n):
    for j in range(1, min(i, k)+1):
        dp[i] = min(dp[i], dp[i-j] + abs(h[i]-h[i-j]))

print(dp[-1])
Buggy python submission (verdict: Time Limit Exceeded):
n, w = map(int, input().split())
t = [tuple(map(int, input().split())) for _ in range(n)]

dp = [[0]*(w+1) for _ in range(n+1)]

for i in range(n):
    for j in range(w+1):
        if j >= t[i][0]:
            dp[i+1][j] = max(dp[i][j-t[i][0]] + t[i][1], dp[i][j])
        else:
            dp[i+1][j] = dp[i][j]

print(dp[n][w])


Fixed submission:
n, w = map(int, input().split())
t = [tuple(map(int, input().split())) for _ in range(n)]

dp = [[0]*(w+1) for _ in range(n+1)]

for i in range(n):
    for j in range(w+1):
        if j >= t[i][0]:
            dp[i+1][j] = max(dp[i][j-t[i][0]] + t[i][1], dp[i][j])
        else:
            dp[i+1][j] = dp[i][j]

print(dp[n][w])
Buggy python submission (verdict: Runtime Error):
from math import log2
n, k = map(int, input().split())
a = list(map(int, input().split()))
b = [[a[i]] for i in range(n)]
c = list(a)

for i in range(n-1):
    for j in range(i+1, n):
        b[i].append(a[j]+b[i][-1])
        c.append(b[i][-1])

m = 40 #ceil(log2((10**9)*1000))=40よりbit幅を40としておけば十分
ans = 0
for i in range(m, -1, -1):
    log = 2**i
    tmp = [x for x in c if x&log==log]
    if len(tmp) >= k:
        ans += log
        c = tmp
print(ans)


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

md = sum(a)/n

ans = 0
m = float('inf')
for i in range(n):
    if abs(a[i]-md) < m:
        ans = i
        m = abs(a[i]-md)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from math import log2
n, k = map(int, input().split())
a = list(map(int, input().split()))
b = [[a[i]] for i in range(n)]
c = list(a)

for i in range(n-1):
    for j in range(i+1, n):
        b[i].append(a[j]+b[i][-1])
        c.append(b[i][-1])

m = 40 #ceil(log2((10**9)*1000))=40よりbit幅を40としておけば十分
ans = 0
for i in range(m, 0, -1):
    count = 0
    for p in c:
        if (ans + 2**(i-1)) & p == ans + 2**(i-1):
            count += 1
            if count == k:
                ans += 2**(i-1)
                break
print(ans)


Fixed submission:
from math import log2
n, k = map(int, input().split())
a = list(map(int, input().split()))
b = [[a[i]] for i in range(n)]
c = list(a)

for i in range(n-1):
    for j in range(i+1, n):
        b[i].append(a[j]+b[i][-1])
        c.append(b[i][-1])

m = 40 #ceil(log2((10**9)*1000))=40よりbit幅を40としておけば十分
ans = 0
for i in range(m, -1, -1):
    log = 2**i
    tmp = [x for x in c if x&log==log]
    if len(tmp) >= k:
        ans += log
        c = tmp
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int, input().split())
a = [[] for _ in range(n)]
b = []
for i in range(m):
    s, t = map(int, input().split())
    a[s-1].append(t)
    a[s-1].sort()
    b.append((s, t))

for i in range(m):
    s, t = b[i][0], b[i][1]
    u = str(a[s-1].index(t)+1)
    print("0"*(6-len(str(s))) + str(s) + "0"*(6-len(u)) + u)



Fixed submission:
n, m = map(int, input().split())
a = [tuple(map(int, input().split())) for _ in range(m)]

cities = [[] for _ in range(n)]

for i, (p, y) in enumerate(a):
    cities[p-1].append((y, i))

ans = [None]*m
for p in range(n):
    for j, (y, i) in enumerate(sorted(cities[p])):
        tmp = str(p+1).zfill(6) + str(j+1).zfill(6)
        ans[i] = tmp

print(*ans, sep="\n")

Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int, input().split())
a = [[] for _ in range(n)]
b = []
for i in range(m):
    s, t = map(int, input().split())
    a[s-1].append(t)
    b.append((s, t))
for i in range(n):
    a[i].sort()

for i in range(m):
    s, t = b[i][0], b[i][1]
    u = str(a[s-1].index(t)+1)
    print("0"*(6-len(str(s))) + str(s) + "0"*(6-len(u)) + u)



Fixed submission:
n, m = map(int, input().split())
a = [tuple(map(int, input().split())) for _ in range(m)]

cities = [[] for _ in range(n)]

for i, (p, y) in enumerate(a):
    cities[p-1].append((y, i))

ans = [None]*m
for p in range(n):
    for j, (y, i) in enumerate(sorted(cities[p])):
        tmp = str(p+1).zfill(6) + str(j+1).zfill(6)
        ans[i] = tmp

print(*ans, sep="\n")

Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int, input().split())
a = [[] for _ in range(n)]
b = []
for i in range(m):
    s, t = map(int, input().split())
    a[s-1].append(t)
    b.append((s, t))
for i in range(n):
    a[i].sort()

for i in range(m):
    s, t = b[i][0], b[i][1]
    u = a[s-1].index(t)+1
    p, q = str(s), str(u)
    lp, lq = len(p), len(q)
    print("0"*(6-lp) + p + "0"*(6-lq) + q)



Fixed submission:
n, m = map(int, input().split())
a = [tuple(map(int, input().split())) for _ in range(m)]

cities = [[] for _ in range(n)]

for i, (p, y) in enumerate(a):
    cities[p-1].append((y, i))

ans = [None]*m
for p in range(n):
    for j, (y, i) in enumerate(sorted(cities[p])):
        tmp = str(p+1).zfill(6) + str(j+1).zfill(6)
        ans[i] = tmp

print(*ans, sep="\n")
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import permutations
n = int(input())
a = tuple(map(int, input().split()))
l = [i + 1 for i in range(n)]
mod = (10**9 + 7)
ans = 0
for v in permutations(l):
    check = [l]
    for i in v:
        for lis in check:
            temp = lis
            if i in temp:
                for k in temp:
                    ans += a[k-1]%mod
                left = temp[:temp.index(i)]
                right = temp[temp.index(i)+1:]
                check.remove(temp)
                check.append(left)
                check.append(right)
                break
            else:
                continue
print(ans%mod)


Fixed submission:
n = int(input())
a = list(map(int, input().split()))
#10**9+7を法とする
mod = 10**9 + 7
#1/{abs(i-j)+1}の累積和をxで考える
x = [0]
#permutation
p = 1
ans = 0
#modの逆元として累積和を考える
for i in range(n):
    x.append((x[-1]+pow(i+1, mod-2, mod))%mod)
    p = (p*(i+1))%mod
#1/{abs(i-j)+1}の累積和はi = j で符号変化に注意
#1はダブルカウントしているので引く
for i in range(n):
    ans = (ans + a[i]*(x[i+1]+x[n-i]-1))%mod
#いま求めたのは1回あたりの期待値なのでn!回考える
print((ans*p)%mod)
Buggy python submission (verdict: Runtime Error):
n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
for i in range(101):
    for j in range(101):
        H = []
        check = []
        for k in range(n):
            x = a[k][0]
            y = a[k][1]
            h = a[k][2]
            if h ==  0:
                check.append((x, y))
            else:
                H.append(h + abs(x-i) + abs(y-j))
                if len(set(H)) > 1:
                    break
            if k == n-1:
                state = False
                for s,t in check:
                    if H[0] - abs(s-i) - abs(t-j) > 0:
                        state = True
                        break
                if state:
                    break
                print(i, j, H[0])
                exit()



Fixed submission:
n = int(input())
if n == 1:
    print("Hello World")
else:
    a = int(input())
    b = int(input())
    print(a+b)
Buggy python submission (verdict: Runtime Error):
n = int(input())
XY = [list(map(int, input().split())) for _ in range(n)]
mod = sum(XY[0])%2
for x, y in XY:
    if mod != (x+y)%2:
        print(-1)
        exit()

m = 33-mod
print(m)
D = [2**i for i in range(31, -1, -1)]
if mod:
    D.append(1)

print(" ".join(map(str, D)))
for x, y in XY:
    w = " "
    for d in D:
        if x-y >= 0 and x+y >= 0:
            w += "R"
            x -= d
        elif x-y < 0 and x+y >= 0:
            w += "U"
            y -= d
        elif x-y >= 0 and x+y < 0:
            w += "D"
            y += d
        else:
            w += "L"
            x += d
    print(w)



Fixed submission:
s = input()
s = s.replace("1","2")

s = s.replace("9","1")

s = s.replace("2","9")

print(s)

Buggy python submission (verdict: Runtime Error):
from collections import Counter
n = int(input())
k = n//2
a = list(map(int, input().split()))
p = []
q = []
for i in range(k):
    p.append(a[2*i])
    q.append(a[2*i+1])
s = Counter(p).most_common()
t = Counter(q).most_common()
u, v = len(s), len(t)
ans = 0
if s[0][0] == t[0][0]:
    if u == 1 and v == 1:
        ans = k
    elif u == 1:
        ans = k - t[1][1]
    elif v == 1:
        ans = k - s[1][1]
    else:
        comp = max(s[1][1], t[1][1])
        ans = n - s[0][1] - comp
else:
    ans = n - s[0][1] - t[0][1]
print(ans)



Fixed submission:
s = input()
s = s.replace("1","2")

s = s.replace("9","1")

s = s.replace("2","9")

print(s)
Buggy python submission (verdict: Runtime Error):
from collections import Counter
n = int(input())
k = n//2
a = list(map(int,input().split()))
b = c = []
for i in range(k):
  b.append(a[2*i])
  c.append(a[2*i+1])
p = Counter(b).most_common()
q = Counter(c).most_common()
s, t = p[0], q[0]
if s[0]!=t[0]:
  ans = n - s[1]-t[1]
else:
  if p[1][1] >= q[1][1]:
    ans = n - t[1]-p[1][1]
  else:
    ans = n - s[1] - q[1][1]
print(ans)

Fixed submission:
from collections import Counter
n = int(input())
k = n//2
a = list(map(int, input().split()))
p = []
q = []
for i in range(k):
    p.append(a[2*i])
    q.append(a[2*i+1])
s = Counter(p).most_common()
t = Counter(q).most_common()
u, v = len(s), len(t)
ans = 0
if s[0][0] == t[0][0]:
    if u == 1 and v == 1:
        ans = k
    elif u == 1:
        ans = k - t[1][1]
    elif v == 1:
        ans = k - s[1][1]
    else:
        comp = max(s[1][1], t[1][1])
        ans = n - s[0][1] - comp
else:
    ans = n - s[0][1] - t[0][1]
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
x = [list(map(int, input().split())) for _ in range(n)]
a = [abs(p[0])+abs(p[1]) for p in x]
t = max(a)
b = [q%2 for q in a]
if len(set(b)) != 1:
    print(-1)
    exit()
print(t)
for i in range(t):
    print("1 ", end="")
print()
for i in range(n):
    ch1 = ch2 = ""
    if x[i][0] >= 0:
        ch1 = "R"
    else:
        ch1 = "L"
    if x[i][1] >= 0:
        ch2 = "U"
    else:
        ch2 = "D"
    for j in range((t-a[i])//2):
        print("RL", end="")
    for j in range(abs(x[i][0])):
        print(ch1, end="")
    for j in range(abs(x[i][1])):
        print(ch2, end="")
    print()



Fixed submission:
n = int(input())
XY = [list(map(int, input().split())) for _ in range(n)]
mod = sum(XY[0])%2
for x, y in XY:
    if mod != (x+y)%2:
        print(-1)
        exit()

m = 33-mod
print(m)
D = [2**i for i in range(31, -1, -1)]
if mod == 0:
    D.append(1)

print(" ".join(map(str, D)))
for x, y in XY:
    w = " "
    for d in D:
        if x-y >= 0 and x+y >= 0:
            w += "R"
            x -= d
        elif x-y < 0 and x+y >= 0:
            w += "U"
            y -= d
        elif x-y >= 0 and x+y < 0:
            w += "D"
            y += d
        else:
            w += "L"
            x += d
    print(w)
Buggy python submission (verdict: Runtime Error):
s = input()
t = input()
dict_s = ["_"]*26
dict_t = ["_"]*26
alphabet = [chr(i) for i in range(97, 97 + 26)]
print(alphabet)
for i in range(len(s)):
    if dict_s[alphabet.index(s[i])] == "_":
        dict_s[alphabet.index(s[i])] = t[i]
    elif dict_s[alphabet.index(s[i])] != t[i]:
            print("No")
            exit()
    if dict_t[alphabet.index(t[i])] == "_":
        dict_t[alphabet.index(t[i])] = s[i]
    elif dict_t[alphabet.index(t[i])] != s[i]:
            print("No")
            exit()
print("Yes")


Fixed submission:
a = list(map(int, input().split()))
d = max(a)
a.remove(d)
print(d*10+sum(a))

Buggy python submission (verdict: Runtime Error):
a = list(map(int, input().split()))
d = max(a)
a.remove(d)
ans(d*10+sum(a))

Fixed submission:
a = list(map(int, input().split()))
d = max(a)
a.remove(d)
print(d*10+sum(a))

Buggy python submission (verdict: Runtime Error):
a = map(int, input().split())
d = max(a)
a.remove(d)
ans(d*10+sum(a))



Fixed submission:
a = list(map(int, input().split()))
d = max(a)
a.remove(d)
print(d*10+sum(a))
Buggy python submission (verdict: Time Limit Exceeded):
import math
mod = 10**9 + 7
n, m = map(int, input().split())
#mの素因数分解
#(prime, power)を要素としてもつ配列を返す関数を作る
def factorize(n):
    fct = []
    b, e = 2, 0
    while b*b <= n:
        while n%b == 0:
            n //= b
            e += 1
        if e > 0:
            fct.append((b, e))
        b += 1
        e = 0
    if n > 1:
        fct.append((n, 1))
    return fct

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

num = factorize(m)
ans = 1
for p in num:
    ans *= (combinations_count(p[1]+n-1, p[1]) % mod)
print(ans%mod)


Fixed submission:
import math
mod = 10**9 + 7
n, m = map(int, input().split())
#mの素因数分解
#(prime, power)を要素としてもつ配列を返す関数を作る
def factorize(n):
    fct = []
    b, e = 2, 0
    while b*b <= n:
        while n%b == 0:
            n //= b
            e += 1
        if e > 0:
            fct.append((b, e))
        b += 1
        e = 0
    if n > 1:
        fct.append((n, 1))
    return fct

num = factorize(m)
ans = 1

for p in num:
    for i in range(p[1]):
        ans *= n+i
    for i in range(p[1]):
        ans //= i+1
print(ans%mod)
Buggy python submission (verdict: Runtime Error):
n, x = map(int, input().split())
a = list(map(int, input().split()))
if n == 1:
    print(abs(x-a[0]))
    exit()
a.sort()
else:
    box = [a[i+1]-a[i] for i in range(n-1)]
    b = min(box)
    for i in range(1,b+1):
        for j in range(n-1):
            if box[j]%i:
                break
            if j == n-2:
                ans = i
    d = abs(x-a[0])
    if ans <= d:
        for i in range(1,ans+1):
            if d%i:
                continue
            else:
                temp = i
        print(temp)
    else:
        for i in range(1,d+1):
            if ans%i:
                continue
            else:
                temp = i
        print(temp)



Fixed submission:
a,b = map(int, input().split())
if a*b % 2:
    print('Yes')
else:
    print('No')
Buggy python submission (verdict: Runtime Error):
s,k = [input() for i in range(2)]
for i in range(k):
    if int(s[i]) > 1:
        print(s[i])
        exit()
print(1)



Fixed submission:
s,k = [input() for i in range(2)]
for i in range(int(k)):
    if int(s[i]) > 1:
        print(s[i])
        exit()
print(1)

Buggy python submission (verdict: Time Limit Exceeded):
s = input()
num =list(map(int, list(s)))
k = int(input())
days = int(5e15)
for i in range(days):
    temp = s[:k]
    for j in num:
         s = s.replace(str(j), str(j)*j)
    if temp == s[:k]:
        break 
print(s[k-1])


Fixed submission:
s,k = [input() for i in range(2)]
for i in range(int(k)):
    if int(s[i]) > 1:
        print(s[i])
        exit()
print(1)

Buggy python submission (verdict: Time Limit Exceeded):
s = input()
k = int(input())
days = int(5e15)
for i in range(days):
    temp = s[:k]
    for j in range(2,10):
         s = s.replace(str(j), str(j)*j)
    if temp == s[:k]:
        break 
print(s[k-1])


Fixed submission:
s,k = [input() for i in range(2)]
for i in range(int(k)):
    if int(s[i]) > 1:
        print(s[i])
        exit()
print(1)

Buggy python submission (verdict: Time Limit Exceeded):
s = input()
k = int(input())
days = int(5e15)
for i in range(days):
    for j in range(2,10):
         s = s.replace(str(j), str(j)*j)

print(s[k-1])


Fixed submission:
s,k = [input() for i in range(2)]
for i in range(int(k)):
    if int(s[i]) > 1:
        print(s[i])
        exit()
print(1)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
mod = 10**9+7
s = input()
q = 0
a = 0
ab = 0
abc = 0
for c in s:
    k = pow(3, q)%mod
    if c == "A":
        a += k
    elif c == "B":
        ab += a
    elif c == "C":
        abc += ab
    else:
        abc = 3*abc + ab
        ab = 3*ab + a
        a = 3*a + k
        q += 1
    a %= mod
    ab %= mod
    abc %= mod
print(abc%mod)



Fixed submission:
from collections import Counter
mod = 10**9+7
s = input()
k = 1
a = 0
ab = 0
abc = 0
for c in s:
    if c == "A":
        a += k
    elif c == "B":
        ab += a
    elif c == "C":
        abc += ab
    else:
        abc = 3*abc + ab
        ab = 3*ab + a
        a = 3*a + k
        k *= 3
    a %= mod
    ab %= mod
    abc %= mod
    k %= mod
print(abc%mod)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
mod = 10**9+7
s = input()
k = 1
a = 0
ab = 0
abc = 0
for c in s:
    if c == "A":
        a += k
    elif c == "B":
        ab += a
    elif c == "C":
        abc += ab
    else:
        abc = (3*abc + ab)%mod
        ab = (3*ab + a)%mod
        a = (3*a + k)%mod
        k *= 3
print(abc%mod)



Fixed submission:
from collections import Counter
mod = 10**9+7
s = input()
k = 1
a = 0
ab = 0
abc = 0
for c in s:
    if c == "A":
        a += k
    elif c == "B":
        ab += a
    elif c == "C":
        abc += ab
    else:
        abc = 3*abc + ab
        ab = 3*ab + a
        a = 3*a + k
        k *= 3
    a %= mod
    ab %= mod
    abc %= mod
    k %= mod
print(abc%mod)