Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
def main():

    N, M = map(int, input().split())
    A = []

    s = set()
    for i in range(M):
        a, b = map(int ,input().split())
        temp = list(map(int, input().split()))
        for j in range(b): s.add(temp[j])
        A.append([a, temp])

    if(len(s) < N): return -1

    cur = dict()
    cur[0] = 0
    for i in range(M):
        temp = cur.copy()
        for v in temp:
            cost = A[i][0]
            u = v
            for j in A[i][1]:
                u |= 1 << j
            if u in cur: cur[u] = min(cur[u], cur[v] + cost)
            else: cur[u] = cur[v] + cost

    target = 0
    for i in range(1, N+1): target |= 1 << i
    return cur[target]


if __name__ == '__main__':
    print(main())


Fixed submission:
def main():

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

    s = set()
    d = dict()
    for i in range(M):
        a, b = map(int ,input().split())
        temp = list(map(int, input().split()))
        v = 0
        for j in range(b):
            s.add(temp[j])
            v |= 1 << temp[j]
        if v in d: d[v] = min(d[v], a)
        else: d[v] = a

    if(len(s) < N): return -1

    M = len(d)
    cur = dict()
    cur[0] = 0
    for g in d:
        temp = cur.copy()
        for v in temp:
            cost = d[g]
            u = v | g
            if u in cur: cur[u] = min(cur[u], cur[v] + cost)
            else: cur[u] = cur[v] + cost

    target = 0
    for i in range(1, N+1): target |= 1 << i
    return cur[target]


if __name__ == '__main__':
    print(main())
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N = int(input())
    ans = 0
    for i in range(1, N+1):
        if i != N:
            ans += i % (i+1)
    return ans
if __name__ == '__main__':
    print(main())

Fixed submission:
def main():
    N = int(input())
    return N*(N-1)//2
if __name__ == '__main__':
    print(main())
Buggy python submission (verdict: Time Limit Exceeded):
import collections

def main():
    s = input()
    t = input()

    ns, nt = len(s), len(t)
    cs, ct = set(list(s)), set(list(t))
    for c in ct:
        if c not in cs: return -1

    d = collections.defaultdict(list)
    for i in range(ns):
        if s[i] in ct: d[s[i]].append(i)

    i = 0
    for c in t:
        while d[c][0] < i:
            d[c].append(d[c].pop(0)+ns)
        i = d[c][0]+1
    return i


if __name__ == '__main__':
    print(main())

Fixed submission:
import collections
import bisect

def main():
    s = input()
    t = input()

    ns, nt = len(s), len(t)
    cs, ct = set(list(s)), set(list(t))
    for c in ct:
        if c not in cs: return -1

    # def unittest(s, t):
    #     i = 0
    #     for c in t:
    #         while s[i % ns] != c:
    #             i += 1
    #         i += 1
    #     return i

    d = collections.defaultdict(list)
    for i in range(ns):
        if s[i] in ct: d[s[i]].append(i)
    # print(s, t)
    i = 0
    for c in t:
        # binary search
        j = i % ns
        k = bisect.bisect_left(d[c], j)
        if k == len(d[c]):
            i = (i // ns + 1)*ns + d[c][0]
        else:
            if j <= d[c][k]:
                i = (i // ns)*ns + d[c][k]
            else:
                i = (i // ns + 1)*ns + d[c][k]
        # print(i)
        i += 1
    return i
    # return i, unittest(s, t)


if __name__ == '__main__':
    print(main())
Buggy python submission (verdict: Runtime Error):

ab = input().split()
A, B = int(ab[0]), int(ab[1])

if A == B:
    print(1)
    return
elif A % 2 != B % 2:
    print("IMPOSSIBLE")
    return
else:
    K = (A+B) // 2
    if abs(A-K) == abs(B-K):
        print(K)
        return
    else:
        print("IMPOSSIBLE")
        return


Fixed submission:
ab = input().split()
A, B = int(ab[0]), int(ab[1])

if A == B:
    print(1)
elif A % 2 != B % 2:
    print("IMPOSSIBLE")
else:
    K = (A+B) // 2
    if abs(A-K) == abs(B-K):
        print(K)
    else:
        print("IMPOSSIBLE")

Buggy python submission (verdict: Runtime Error):
A, B = list(map(int, input().split())

if A == B:
    print(1)
elif A % 2 != B % 2:
    print("IMPOSSIBLE")
else:
    K = (A+B) // 2
    if abs(A-K) == abs(B-K):
        print(K)
    else:
        print("IMPOSSIBLE")


Fixed submission:
ab = input().split()
A, B = int(ab[0]), int(ab[1])

if A == B:
    print(1)
elif A % 2 != B % 2:
    print("IMPOSSIBLE")
else:
    K = (A+B) // 2
    if abs(A-K) == abs(B-K):
        print(K)
    else:
        print("IMPOSSIBLE")

Buggy python submission (verdict: Runtime Error):
A, B = list(map(int, input().split())

if A == B:
    print(1)    
elif A % 2 != B % 2:
    print("IMPOSSIBLE")
else:
    K = (A+B) // 2
    if abs(A-K) == abs(B-K):
        print(K)
    else:
        print("IMPOSSIBLE")

Fixed submission:
ab = input().split()
A, B = int(ab[0]), int(ab[1])

if A == B:
    print(1)
elif A % 2 != B % 2:
    print("IMPOSSIBLE")
else:
    K = (A+B) // 2
    if abs(A-K) == abs(B-K):
        print(K)
    else:
        print("IMPOSSIBLE")

Buggy python submission (verdict: Runtime Error):
A, B = list(map(int, input().split())

if A == B:
    print(1)
    return
    
if A % 2 != B % 2:
    print("IMPOSSIBLE")
    return
else:
    K = (A+B) // 2
    if abs(A-K) == abs(B-K):
        print(K)
        return 
    else:
        print("IMPOSSIBLE")
        return

Fixed submission:
ab = input().split()
A, B = int(ab[0]), int(ab[1])

if A == B:
    print(1)
elif A % 2 != B % 2:
    print("IMPOSSIBLE")
else:
    K = (A+B) // 2
    if abs(A-K) == abs(B-K):
        print(K)
    else:
        print("IMPOSSIBLE")
Buggy python submission (verdict: Runtime Error):
N = int(input())
p = [int(x) for x in input.split()]

count = 0
p_sorted = sorted(p)
for i in range(N):
    if p_sorted[i] != p[i]:
        count += 1
if count > 2:
    print("NO")
else:
    print("YES")
        

Fixed submission:
N = int(input())
p = [int(x) for x in input().split()]

count = 0
p_sorted = sorted(p)
for i in range(N):
    if p_sorted[i] != p[i]:
        count += 1
if count > 2:
    print("NO")
else:
    print("YES")
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = [int(x) for x in input.split()]
B = [int(x) for x in input.split()]

tot = 0
for i in range(N):
    if A[i] <= B[i]:
        tot += A[i]
        B[i] -= A[i]
        A[i] = 0
    else:
        tot += B[i]
        B[i] = 0
        A[i] = A[i] - B[i]
    if B[i] >= 0:
        if A[i+1] <= B[i]:
            tot += A[i+1]
            A[i+1] = 0
            B[i] -= A[i+1]
        else:
            A[i+1] -= B[i]
            tot += B[i]
            B[i] = 0

print(tot)


Fixed submission:
N = int(input())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]

tot = 0
for i in range(N):
    if A[i] <= B[i]:
        tot += A[i]
        B[i] -= A[i]
        A[i] = 0
    else:
        tot += B[i]
        B[i] = 0
        A[i] = A[i] - B[i]
    if B[i] >= 0:
        if A[i+1] <= B[i]:
            tot += A[i+1]
            A[i+1] = 0
            B[i] -= A[i+1]
        else:
            A[i+1] -= B[i]
            tot += B[i]
            B[i] = 0

print(tot)
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    S = input()
    div = pow(10, 9) + 7
    rem = [0 for _ in range(13)]
    rem[0] = 1
    for c in S:
        temp = [0 for _ in range(13)]
        if c != "?":
            for i in range(13):
                r = (i*10+int(c)) % 13
                temp[r] += rem[i] % div
        else:
            for i in range(13):
                for j in range(10):
                    r = (i*10+j) % 13
                    temp[r] += rem[i] % div
        rem = temp
    return rem[5] % div

if __name__ == '__main__':
    print(main())

Fixed submission:
def main():
    S = input()
    div = pow(10, 9) + 7
    rem = [0 for _ in range(13)]
    rem[0] = 1
    for c in S:
        temp = [0 for _ in range(13)]
        if c != "?":
            for i in range(13):
                r = (i*10+int(c)) % 13
                temp[r] += rem[i] % div
        else:
            for i in range(13):
                for j in range(10):
                    r = (i*10+j) % 13
                    temp[r] += rem[i] % div
        rem = temp
    return rem[5] % div

if __name__ == '__main__':
    print(main())

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    S = input()
    div = pow(10, 9) + 7
    rem = [0 for _ in range(13)]
    rem[0] = 1
    for c in S:
        temp = [0 for _ in range(13)]
        if c != "?":
            for i in range(13):
                r = (i*10+int(c)) % 13
                temp[r] += rem[i]
        else:
            for i in range(13):
                for j in range(10):
                    r = (i*10+j) % 13
                    temp[r] += rem[i]
        rem = temp
    return rem[5] % div

if __name__ == '__main__':
    print(main())

Fixed submission:
def main():
    S = input()
    div = pow(10, 9) + 7
    rem = [0 for _ in range(13)]
    rem[0] = 1
    for c in S:
        temp = [0 for _ in range(13)]
        if c != "?":
            for i in range(13):
                r = (i*10+int(c)) % 13
                temp[r] += rem[i] % div
        else:
            for i in range(13):
                for j in range(10):
                    r = (i*10+j) % 13
                    temp[r] += rem[i] % div
        rem = temp
    return rem[5] % div

if __name__ == '__main__':
    print(main())
Buggy python submission (verdict: Runtime Error):
def main():
    n = int(input())
    A = list(map(int, input().split()))

    filled = [0]*(n+1)
    ans = []
    for i in range(n-1, -1, -1):
        if sum(filled[::i+1][1:]) % 2 != A[i]:
            filled[i+1] = 1
            ans.append(i+1)
    print(len(ans))
    print(' '.join(map(str, ans)))


if __name__ == '__main__':
    main()

Fixed submission:
import math

def main():
    N, D = map(int, input().split())
    points = []
    for i in range(N):
        p = [int(c) for c in input().split()]
        points.append(p)

    count = 0
    for i in range(N-1):
        for j in range(i+1, N):
            v = 0
            for k in range(D):
                v += pow(points[i][k]-points[j][k], 2)
            vsqrt = math.sqrt(v)
            if int(vsqrt) == vsqrt:
                count += 1
    return count

if __name__ == '__main__':
    print(main())
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    L, R = map(int, input().split())
    d = dict()
    for i in range(L, R+1):
        v = i % 2019
        if v not in d: d[v] = 1
        else: d[v] += 1

    min_r = 2018
    for i in range(2019):
        if i in d and d[i] > 1:
            min_r = min(min_r, (i*i) % 2019)
    for i in range(2018):
        for j in range(i+1, 2019):
            if i in d and j in d:
                min_r = min(min_r, (i*j) % 2019)

    return min_r



if __name__ == '__main__':
    print(main())

Fixed submission:
def main():
    L, R = map(int, input().split())
    d = dict()
    for i in range(L, min(R+1, L+2019*2)):
        v = i % 2019
        if v not in d: d[v] = 1
        else: d[v] += 1

    min_r = 2018
    for i in d:
        if i in d and d[i] > 1:
            min_r = min(min_r, (i*i) % 2019)

    for i in d:
        for j in d:
            if i < j: min_r = min(min_r, (i*j) % 2019)

    return min_r



if __name__ == '__main__':
    print(main())

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    L, R = map(int, input().split())
    d = dict()
    for i in range(L, R+1):
        v = i % 2019
        if v not in d: d[v] = 1
        else: d[v] += 1

    min_r = 2018
    for i in range(2019):
        if i in d and d[i] > 1:
            min_r = min(min_r, (i*i) % 2019)
    for i in range(2018):
        for j in range(i+1, 2019):
            if i in d and j in d:
                min_r = min(min_r, (i*j) % 2019)

    return min_r



if __name__ == '__main__':
    print(main())

Fixed submission:
def main():
    L, R = map(int, input().split())
    d = dict()
    for i in range(L, min(R+1, L+2019*2)):
        v = i % 2019
        if v not in d: d[v] = 1
        else: d[v] += 1

    min_r = 2018
    for i in d:
        if i in d and d[i] > 1:
            min_r = min(min_r, (i*i) % 2019)

    for i in d:
        for j in d:
            if i < j: min_r = min(min_r, (i*j) % 2019)

    return min_r



if __name__ == '__main__':
    print(main())
Buggy python submission (verdict: Runtime Error):
import math

def main():
    A, B, C, D = map(int, input().split())
    p = math.gcd(C, D)
    lcm = C * D // p
    dA = (A-1) - (A-1) // C - (A-1) // D + (A-1) // lcm
    dB = B - B // C - B // D + B // lcm
    return dB - dA


if __name__ == '__main__':
    print(main())

Fixed submission:
def main():
    A, B, C, D = map(int, input().split())
    if C <= D: p = gcd(C, D)
    else: p = gcd(D, C)
    lcm = C * D // p
    dA = (A-1) - (A-1) // C - (A-1) // D + (A-1) // lcm
    dB = B - B // C - B // D + B // lcm
    return dB - dA

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

if __name__ == '__main__':
    print(main())
Buggy python submission (verdict: Time Limit Exceeded):
def main():

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

    mod = pow(10, 9) + 7
    dp = [[0 for _ in range(M+1)] for _ in range(N+1)]
    dp[0][0] = 0
    # for i in range(N): dp[i][0] = 0
    # for j in range(M): dp[0][j] = 0

    for i in range(N):
        for j in range(M):
            dp[i+1][j+1] = dp[i][j+1] + dp[i+1][j] - dp[i][j]
            if S[i] == T[j]:
                dp[i+1][j+1] += dp[i][j] + 1
            dp[i+1][j+1] %= mod
    # print(dp)
    return dp[N][M] + 1

if __name__ == '__main__':
    print(main())


Fixed submission:
def main():

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

    mod = pow(10, 9) + 7
    dp = [[0 for _ in range(M+1)] for _ in range(N+1)]
    dp[0][0] = 0
    # for i in range(N): dp[i][0] = 0
    # for j in range(M): dp[0][j] = 0

    for i in range(N):
        for j in range(M):
            dp[i+1][j+1] = dp[i][j+1] + dp[i+1][j] - dp[i][j]
            if S[i] == T[j]:
                dp[i+1][j+1] += dp[i][j] + 1
            dp[i+1][j+1] %= mod
    # print(dp)
    return dp[N][M] + 1

if __name__ == '__main__':
    print(main())
Buggy python submission (verdict: Time Limit Exceeded):
def main():

    L = input()
    mod = pow(10, 9) + 7
    n = len(L)
    count = dict()
    prefix = 0
    for c in L:
        temp = dict()
        for v in count:
            temp[v+1] = temp.get(v+1, 0) + count[v]
            temp[v] = temp.get(v, 0) + count[v]
        if c == "1":
            temp[prefix] = temp.get(prefix, 0) + 1
            prefix += 1
        count = temp
    count[prefix] = count.get(prefix, 0) + 1

    pows = [1]
    for l in range(1, len(L)+1):
        pows.append(pows[-1]*2)
    ans = 0
    for v in count:
        ans += pows[v] * count[v]
        ans %= mod
    return ans

if __name__ == '__main__':
    print(main())

Fixed submission:
def main():

    L = input()
    mod = pow(10, 9) + 7
    n = len(L)
    dp1 = [0 for _ in range(n+1)]
    dp2 = [0 for _ in range(n+1)]
    dp2[0] = 1
    for i in range(n):
        if L[i] == "0":
            dp1[i+1] = dp1[i] * 3
            dp2[i+1] = dp2[i]
        else:
            dp1[i+1] = dp1[i] * 3 + dp2[i]
            dp2[i+1] = dp2[i] * 2
        dp1[i+1] %= mod
        dp2[i+1] %= mod
    # print(dp1)
    # print(dp2)
    return (dp1[n] + dp2[n]) % mod

if __name__ == '__main__':
    print(main())
Buggy python submission (verdict: Time Limit Exceeded):

def main():

    N = int(input())
    food1, food2 = [], []
    for i in range(N):
        a, b = map(int, input().split())
        food1.append([a+b, a, b, i])
        food2.append([-a-b, a, b, i])
    food1.sort(reverse = True)
    food2.sort()
    used = set()
    ans = 0
    while food1 or food2:
        while food1 and food1[0][3] in used:
            food1.pop(0)
        if food1:
            _, a, _, i = food1.pop(0)
            used.add(i)
            ans += a
        while food2 and food2[0][3] in used:
            food2.pop(0)
        if food2:
            _, _, b, i = food2.pop(0)
            used.add(i)
            ans -= b
    return ans


if __name__ == '__main__':
    print(main())

Fixed submission:

def main():

    N = int(input())
    food1, food2 = [], []
    for i in range(N):
        a, b = map(int, input().split())
        food1.append([a+b, a, b, i])
        food2.append([-a-b, a, b, i])
    food1.sort()
    food2.sort(reverse = True)
    used = set()
    ans = 0
    while food1 or food2:
        while food1 and food1[-1][3] in used:
            food1.pop()
        if food1:
            _, a, _, i = food1.pop()
            used.add(i)
            ans += a
        while food2 and food2[-1][3] in used:
            food2.pop()
        if food2:
            _, _, b, i = food2.pop()
            used.add(i)
            ans -= b
    return ans


if __name__ == '__main__':
    print(main())
Buggy python submission (verdict: Time Limit Exceeded):
def main():

    H, W = map(int, input().split())
    A = []
    for _ in range(H): A.append(input())
    # print(A)
    ans = 0
    mv = [[1,0],[0,1],[-1,0],[0,-1]]
    for i in range(H):
        for j in range(W):
            if A[i][j] == "#":
                # print(i, j)
                visited = set()
                visited.add((i, j))
                cnt = 0
                cur = [[i, j]]
                while cur:
                    temp = []
                    cnt += 1
                    if cnt % 2 == 1: c = "."
                    else: c = "#"
                    for i1, j1 in cur:
                        for di, dj in mv:
                            k, l = i1+di, j1+dj
                            if 0<=k<H and 0<=l<W and (k, l) not in visited and A[k][l] == c:
                                visited.add((k, l))
                                temp.append([k, l])
                                if c == ".":
                                    ans += 1
                    cur = temp
                # print(i, j, ans)

    return ans

if __name__ == '__main__':
    print(main())

Fixed submission:
def main():

    H, W = map(int, input().split())
    A = []
    for _ in range(H): A.append(input())

    ans = 0
    visited = set()
    for i in range(H):
        for j in range(W):
            if (i, j) not in visited:
                visited.add((i, j))
                b, w = 0, 0
                if A[i][j] == "#":
                    b += 1
                    c = "."
                else:
                    w += 1
                    c = "#"
                cur = [[i, j]]
                while cur:
                    temp = []
                    for k1, l1 in cur:
                        for dk, dl in [[1,0],[-1,0],[0,1],[0,-1]]:
                            k, l = k1+dk, l1+dl
                            if 0<=k<H and 0<=l<W and (k,l) not in visited and A[k][l] == c:
                                visited.add((k,l))
                                temp.append([k, l])

                    if c == "#":
                        b += len(temp)
                        c = "."
                    else:
                        w += len(temp)
                        c = "#"
                    cur = temp
                ans += b*w
    return ans

if __name__ == '__main__':
    print(main())
Buggy python submission (verdict: Time Limit Exceeded):
def main():

    N, K = map(int, input().split())
    H = list(map(int, input().split()))
    dp = [float('inf') for _ in range(N)]
    dp[0] = 0
    for i in range(1, N):
        for j in range(1, K+1):
            if i - j >=0:
                dp[i] = min(dp[i], dp[i-j] + abs(H[i] - H[i-j]))

    return dp[N-1]

if __name__ == '__main__':
    print(main())

Fixed submission:
def main():

    N, K = map(int, input().split())
    H = list(map(int, input().split()))
    dp = [float('inf') for _ in range(N)]
    dp[0] = 0
    for i in range(1, N):
        for j in range(1, K+1):
            if i - j >=0:
                dp[i] = min(dp[i], dp[i-j] + abs(H[i] - H[i-j]))

    return dp[N-1]

if __name__ == '__main__':
    print(main())
Buggy python submission (verdict: Runtime Error):
import collections
def main():

    N, M = map(int, input().split())
    graph = collections.defaultdict(list)
    for _ in range(M):
        x, y = map(int, input().split())
        graph[x].append(y)

    memo = dict()
    def helper(node):
        if node in memo:
            return memo[node]

        max_l = 0
        for nxt in graph[node]:
            max_l = max(max_l, helper(nxt) + 1)
        memo[node] = max_l
        return max_l

    max_l = 0
    for i in range(1, N+1):
        l = helper(i)
        max_l = max(max_l, l)
    return max_l

if __name__ == '__main__':
    print(main())

Fixed submission:
import collections
import sys
def main():

    sys.setrecursionlimit(10 ** 6)

    N, M = map(int, input().split())
    graph = collections.defaultdict(list)
    for _ in range(M):
        x, y = map(int, input().split())
        graph[x].append(y)

    memo = dict()
    def helper(node):
        if node in memo:
            return memo[node]

        max_l = 0
        for nxt in graph[node]:
            max_l = max(max_l, helper(nxt) + 1)
        memo[node] = max_l
        return max_l

    max_l = 0
    for i in range(1, N+1):
        l = helper(i)
        max_l = max(max_l, l)
    return max_l

if __name__ == '__main__':
    print(main())
Buggy python submission (verdict: Time Limit Exceeded):
def main():

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

    dp = [[0 for _ in range(N+1)] for _ in range(N)]
    dp[0][0] = 1-p[0]
    dp[0][1] = p[0]
    for i in range(1, N):
        for j in range(i+2):
            if j == 0:
                dp[i][j] = dp[i-1][j] * (1-p[i])
            else:
                dp[i][j] = dp[i-1][j] * (1-p[i]) + dp[i-1][j-1] * p[i]
    ans = 0
    for j in range((N+1)//2, N+1):
        ans += dp[N-1][j]
    return ans

if __name__ == '__main__':
    print(main())

Fixed submission:
def main():

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

    dp = [[0 for _ in range(N+1)] for _ in range(N)]
    dp[0][0] = 1-p[0]
    dp[0][1] = p[0]
    for i in range(1, N):
        for j in range(i+2):
            if j == 0:
                dp[i][j] = dp[i-1][j] * (1-p[i])
            else:
                dp[i][j] = dp[i-1][j] * (1-p[i]) + dp[i-1][j-1] * p[i]
    ans = 0
    for j in range((N+1)//2, N+1):
        ans += dp[N-1][j]
    return ans

if __name__ == '__main__':
    print(main())
Buggy python submission (verdict: Runtime Error):
def main():
    S = input()
    K = int(input())
    i = 0
    while S[i] == "1":
        i += 1
    if K <= i:
        return "1"
    else:
        return S[i]

if __name__ == '__main__':
    print(main())


Fixed submission:
def main():
    S = input()
    K = int(input())
    i = 0
    while i < len(S) and S[i] == "1":
        i += 1
    if K <= i:
        return "1"
    else:
        return S[i]

if __name__ == '__main__':
    print(main())

Buggy python submission (verdict: Runtime Error):
def main():
    S = input()
    K = int(input())
    if S[0] == "1":
        if K == 1:
            return 1
        else:
            i = 0
            while S[i] == "1":
                i += 1
            return  int(S[i])
    else:
        return int(S[0])


if __name__ == '__main__':
    print(main())


Fixed submission:
def main():
    S = input()
    K = int(input())
    i = 0
    while i < len(S) and S[i] == "1":
        i += 1
    if K <= i:
        return "1"
    else:
        return S[i]

if __name__ == '__main__':
    print(main())