Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

def print_l(l):
    print(' '.join(map(str, l)))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res

import math
from collections import deque
    
n,d,a = l_in()
xh = []
for _ in range(n):
    x,h=l_in()
    xh.append((x,math.ceil(h/a)))

xh.sort()
res = 0
currentX = -1
currentH = 0
q=deque()

for x,h in xh:
    while len(q) > 0:
        bx, bh = q[0]
        if bx < x:
            q.popleft()
        else:
            break
    for bx, bh in q:    
        h -= bh
    if h > 0:
        q.append((x+2*d, h))
        res += h

print(res)



Fixed submission:
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

def print_l(l):
    print(' '.join(map(str, l)))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res

import math
from collections import deque
    
n,d,a = l_in()
xh = []
for _ in range(n):
    x,h=l_in()
    xh.append((x,math.ceil(h/a)))

xh.sort()
res = 0
currentX = -1
currentH = 0
q=deque()
q_sum = 0

for x,h in xh:
    while len(q) > 0:
        bx, bh = q[0]
        if bx < x:
            q.popleft()
            q_sum -= bh
        else:
            break
    h -= q_sum
    if h > 0:
        q.append((x+2*d, h))
        q_sum += h
        res += h

print(res)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

def print_l(l):
    print(' '.join(map(str, l)))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res

h,w = l_in()
S = []
for _ in range(h):
    s = s_in()
    S.append(s)
    
from collections import deque

res = 0
for i in range(h):
    for j in range(w):
        q = deque()
        s = set()
        check = lambda x,y: (not (x,y) in s) and x >= 0 and x < h and y >=0 and y < w and S[x][y] == '.'
        
        if S[i][j] == '.':
            q.append((i,j,0))

        while len(q) > 0:
            i,j,d = q.popleft()
            s.add((i,j))
            res = max(d,res)
            
            if check(i+1,j):
                q.append((i+1,j,d+1))
            if check(i-1,j):
                q.append((i-1,j,d+1))
            if check(i,j+1):
                q.append((i,j+1,d+1))
            if check(i,j-1):
                q.append((i,j-1,d+1))

print(res)



Fixed submission:
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

def print_l(l):
    print(' '.join(map(str, l)))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res

h,w = l_in()
S = [s_in() for _ in range(h)]
    
from collections import deque

res = 0
for i in range(h):
    for j in range(w):
        q = deque()
        s = set()
        check = lambda x,y: (not (x,y) in s) and x >= 0 and x < h and y >=0 and y < w and S[x][y] == '.'
        
        if S[i][j] == '.':
            q.append((i,j,0))

        while len(q) > 0:
            i,j,d = q.popleft()
            s.add((i,j))
            res = max(d,res)
            
            if check(i+1,j):
                s.add((i+1,j))
                q.append((i+1,j,d+1))
            if check(i-1,j):
                s.add((i-1,j))                
                q.append((i-1,j,d+1))
            if check(i,j+1):
                s.add((i,j+1))            
                q.append((i,j+1,d+1))
            if check(i,j-1):
                s.add((i,j-1))            
                q.append((i,j-1,d+1))

print(res)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

def print_l(l):
    print(' '.join(map(str, l)))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res

n = n_in()
xy = [l_in() for _ in range(n)]

left = 0
right = 2000

from itertools import product
def check(r):
    return all((x1-x2)**2 + (y1-y2)**2 <= 4*r*r for (x1,y1),(x2,y2) in product(xy, repeat=2))

while right-left > 10**-16:
    mid = (left+right)/2
    if check(mid):
        right = mid
    else:
        left = mid

print((left+right)/2)
    


Fixed submission:
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

def print_l(l):
    print(' '.join(map(str, l)))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res

n = n_in()
xy = [l_in() for _ in range(n)]

left = 0
right = 2000

from itertools import combinations
import math
def check(r):
    allprox = True
    for (x1,y1),(x2,y2) in combinations(xy, 2):
        dx = x1-x2
        dy = y1-y2

        d2 = dx*dx+dy*dy

        if d2 < 10**-16:
            continue

        allprox = False
        
        if d2/4 > r*r:
            continue

        h = math.sqrt(r*r-d2/4)
        d = math.sqrt(d2)

    
        px,py= (x1+x2)/2, (y1+y2)/2

        qx,qy = px-dy/d*h, py+dx/d*h
        if all((qx-x3)*(qx-x3) + (qy-y3)*(qy-y3) <= r*r for x3,y3 in xy if (x1 != x3 or y1 != y3) and (x2 != x3 or y2 != y3)):
            return True
        
        qx,qy = px+dy/d*h, py-dx/d*h
        if all((qx-x3)*(qx-x3) + (qy-y3)*(qy-y3) <= r*r for x3,y3 in xy if (x1 != x3 or y1 != y3) and (x2 != x3 or y2 != y3)):
            return True
    else:
        return allprox

while right-left > 10**-10:
    mid = (left+right)/2
    if check(mid):
        right = mid
    else:
        left = mid

print((left+right)/2)
Buggy python submission (verdict: Runtime Error):
import fractions # version 3.4
from collections import defaultdict
from functools import reduce

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

def lcm(*numbers):
    ans = numbers[0]
    for a in numbers:
        ans = ans * a // fractions.gcd(ans, a)
    # return reduce(lambda x,y: (x * y) // fractions.gcd(x, y), numbers, 1)

    return ans


def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res

N, M = l_in()
A = l_in()

B = [a//2 for a in A]
L = lcm(*B)

if any((L//b)%2 == 0 for b in B):
    print(0)
else:
    print((M//L + 1)//2)


Fixed submission:
def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res


K, X = l_in()

if 500*K >= X:
    print("Yes")
else:
    print("No")
Buggy python submission (verdict: Runtime Error):
def s_in():
    return input()

S = s_in()

if len(S) == 1:
    print(1)
    exit()


lis = []
cnt = 1
for i in range(len(S)-1):
    if S[i] == S[i+1]:
        cnt += 1
    else:
        lis.append((S[i], cnt))
        cnt = 1
else:
    lis.append((S[len(S)-1], cnt))


res = 0
idx = 0


if lis[0][0] == ">":
    res += sum(range(lis[0][1]+1))
    idx += 1

while True:
    if idx+1 == len(lis):
        res += sum(range(lis[idx][1]+1))
        break

    x = lis[idx][1]
    y = lis[idx+1][1]

    res += sum(range(max(x,y)+1)) + sum(range(min(x,y)))

    idx += 2

    if idx == len(lis):
        break


print(res)



Fixed submission:
def s_in():
    return input()

S = s_in()

if len(S) == 1:
    print(1)
    exit()


lis = []
cnt = 1
for i in range(len(S)-1):
    if S[i] == S[i+1]:
        cnt += 1
    else:
        lis.append((S[i], cnt))
        cnt = 1
else:
    lis.append((S[len(S)-1], cnt))


res = 0
idx = 0


if lis[0][0] == ">":
    res += sum(range(lis[0][1]+1))
    idx += 1

while idx < len(lis):
    if idx+1 == len(lis):
        res += sum(range(lis[idx][1]+1))
        break

    x = lis[idx][1]
    y = lis[idx+1][1]

    res += sum(range(max(x,y)+1)) + sum(range(min(x,y)))

    idx += 2


print(res)

Buggy python submission (verdict: Runtime Error):
def s_in():
    return input()

S = s_in()

if len(S) == 1:
    print(1)
    exit()


lis = []
cnt = 1
for i in range(len(S)-1):
    if S[i] == S[i+1]:
        cnt += 1
    else:
        lis.append((S[i], cnt))
        cnt = 1
else:
    lis.append((S[len(S)-1], cnt))


res = 0
idx = 0


if lis[0][0] == ">":
    res += sum(range(lis[0][1]+1))
    idx += 1

while True:
    if idx+1 == len(lis):
        res += sum(range(lis[idx][1]+1))
        break

    x = lis[idx][1]
    y = lis[idx+1][1]

    if x == y:
        res += sum(x+1)*2
    else:
        res += sum(range(max(x,y)+1)) + sum(range(min(x,y)))

    idx += 2

    if idx == len(lis):
        break


print(res)



Fixed submission:
def s_in():
    return input()

S = s_in()

if len(S) == 1:
    print(1)
    exit()


lis = []
cnt = 1
for i in range(len(S)-1):
    if S[i] == S[i+1]:
        cnt += 1
    else:
        lis.append((S[i], cnt))
        cnt = 1
else:
    lis.append((S[len(S)-1], cnt))


res = 0
idx = 0


if lis[0][0] == ">":
    res += sum(range(lis[0][1]+1))
    idx += 1

while idx < len(lis):
    if idx+1 == len(lis):
        res += sum(range(lis[idx][1]+1))
        break

    x = lis[idx][1]
    y = lis[idx+1][1]

    res += sum(range(max(x,y)+1)) + sum(range(min(x,y)))

    idx += 2


print(res)
Buggy python submission (verdict: Time Limit Exceeded):
import math

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

A = list(map(int, input().split()))
F = list(map(int, input().split()))

A.sort(reverse=True)
F.sort()

def check(x):
  k = K
  for i in range(N):
    k -= max(0,math.ceil((A[i]*F[i]-x)/F[i]))

  return k >= 0



left = 0
right = 10**12

if check(left):
  print(0)
  exit()

while left + 1 < right:
  mid = (left + right)//2
  if check(mid):
    right = mid
  else:
    left = mid


print(right)


Fixed submission:
import math

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

A = list(map(int, input().split()))
F = list(map(int, input().split()))

A.sort(reverse=True)
F.sort()

def check(x):
  k = K
  for i in range(N):
    k -= max(0,math.ceil((A[i]*F[i]-x)/F[i]))

  return k >= 0



left = 0
right = 10**12

if check(left):
  print(0)
  exit()

while left + 1 < right:
  mid = (left + right)//2
  if check(mid):
    right = mid
  else:
    left = mid


print(right)
Buggy python submission (verdict: Time Limit Exceeded):
import heapq
N, M = map(int, input().split())

edges = [set() for _ in range(N)]

for _ in range(M):
    u, v = map(int, input().split())
    edges[u-1].add(v-1)

S, T = map(int, input().split())
S -= 1
T -= 1


step2 = [set() for _ in range(N)]

for u in range(N):
    for v in edges[u]:
        step2[u] |= edges[v]

cost = [-1 for _ in range(N)]
q = []
heapq.heappush(q, (0, S))

while len(q) != 0:
    c, u = heapq.heappop(q)
    if cost[u] != -1:
        continue
    cost[u] = c
    for u2 in step2[u]:
        rms = set()
        for v in edges[u2]:
            if cost[v] != -1:
                rms.add(v)
            else:
                heapq.heappush(q, (c+1, v))

        edges[u2] -= rms

print(cost[T])


Fixed submission:
import heapq
N, M = map(int, input().split())

edges = [set() for _ in range(N)]

for _ in range(M):
    u, v = map(int, input().split())
    edges[u-1].add(v-1)

S, T = map(int, input().split())
S -= 1
T -= 1

cost = [-1 for _ in range(N)]
q = []
heapq.heappush(q, (0, S))

step1memo = set()
step2memo = set()
step3memo = set()

while len(q) != 0:
    c, u = heapq.heappop(q)
    if cost[u] != -1:
        continue
    cost[u] = c
    for u1 in edges[u]:
        if u1 in step1memo:
            continue
        step1memo.add(u1)
        for u2 in edges[u1]:
            if u2 in step2memo:
                continue
            step2memo.add(u2)
            for u3 in edges[u2]:
                heapq.heappush(q, (c+1, u3))

print(cost[T])

Buggy python submission (verdict: Time Limit Exceeded):
import heapq
N, M = map(int, input().split())

edges = [set() for _ in range(N)]

for _ in range(M):
    u, v = map(int, input().split())
    edges[u-1].add(v-1)

S, T = map(int, input().split())
S -= 1
T -= 1


step2 = [set() for _ in range(N)]

for u in range(N):
    for v in edges[u]:
        step2[u] |= edges[v]

step3 = [set() for _ in range(N)]

for u in range(N):
    for v in edges[u]:
        step3[u] |= step2[v]

cost = [-1 for _ in range(N)]
cost[S] = 0

q = []

for v in step3[S]:
    heapq.heappush(q, (1, v))

while len(q) != 0:
    c, u = heapq.heappop(q)
    if cost[u] != -1:
        continue
    cost[u] = c
    for v in step3[u]:
        heapq.heappush(q, (c+1, v))

print(cost[T])


Fixed submission:
import heapq
N, M = map(int, input().split())

edges = [set() for _ in range(N)]

for _ in range(M):
    u, v = map(int, input().split())
    edges[u-1].add(v-1)

S, T = map(int, input().split())
S -= 1
T -= 1

cost = [-1 for _ in range(N)]
q = []
heapq.heappush(q, (0, S))

step1memo = set()
step2memo = set()
step3memo = set()

while len(q) != 0:
    c, u = heapq.heappop(q)
    if cost[u] != -1:
        continue
    cost[u] = c
    for u1 in edges[u]:
        if u1 in step1memo:
            continue
        step1memo.add(u1)
        for u2 in edges[u1]:
            if u2 in step2memo:
                continue
            step2memo.add(u2)
            for u3 in edges[u2]:
                heapq.heappush(q, (c+1, u3))

print(cost[T])
Buggy python submission (verdict: Runtime Error):
import numpy as np
from collections import defaultdict
from functools import reduce

import numpy as np
MOD = 1000000007

def mod_add(a, b):
  return (a+b)%MOD

def mod_sub(a, b):
  return (a+MOD-b)%MOD

def mod_mul(a, b):
  return (a*b)%MOD

#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = (1,0,a)
    w = (0,1,b)
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    return w[0], w[1]

def mod_inv(a):
    x, _  = extgcd(a, MOD)
    return (MOD+x%MOD)%MOD

def mod_div(a, b):
    return a*mod_inv(b)%MOD

def mod_pow(a, b):
    res = 1
    while b > 0:
        if b & 1:
            res = res * a * MOD
        a = a * a % MOD
        b >>= 1
    return res

MAX = 200010

fac  = [1,1]
finv = [1,1]
inv  = [1,1]

def COMinit():
    # fac[0] = fac[1] = 1
    # finv[0] = finv[1] = 1
    # inv[1] = 1
    for i in range(2, MAX):
        fac.append(fac[i - 1] * i % MOD)
        inv.append(MOD - inv[MOD%i] * (MOD / i) % MOD)
        finv.append(finv[i - 1] * inv[i] % MOD)

def mod_COM(n, k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;


# s = input()
# n = int(input())
COMinit()
N, A, B, C = list(map(int, input().split()))

a = mod_div(A, 100)
b = mod_div(B, 100)
c = mod_div(C, 100)

k_factor_memo = {}
def k_factor(M):
    if M in k_factor_memo:
        return k_factor_memo[M]
    if C == 100-C:
        res = fac[M+1]

        res = mod_div(res, mod_sub(1,c))
        k_factor_memo[M] = res
        return res
    res = mod_mul(fac[M], mod_div(c, mod_sub(1, mod_mul(2,c))))
    c2 = mod_div(c, mod_sub(1, c))
    c2 = pow(c2, M, MOD)
    c2 = mod_sub(c2, 1)
    res = mod_mul(res, c2)
    res = mod_div(res, mod_sub(1,c))
    k_factor_memo[M] = res
    return res

res = 0
an = pow(a, N, MOD)

for j in range(N):
    tmp = mod_mul(mod_mul(N, finv[N]), finv[j])
    # print(tmp)
    tmp = mod_mul(tmp, an)
    # print(tmp)
    tmp = mod_mul(tmp, pow(b, j, MOD))
    # print(tmp)
    tmp = mod_mul(tmp, k_factor(N+j))
    # print(tmp)
    res = mod_add(res, tmp)
# print(res)

bn = pow(b, N, MOD)
for j in range(N):
    tmp = mod_mul(mod_mul(N, finv[N]), finv[j])
    tmp = mod_mul(tmp, bn)
    tmp = mod_mul(tmp, pow(a, j, MOD))
    tmp = mod_mul(tmp, k_factor(N+j))
    res = mod_add(res, tmp)

print(res)


Fixed submission:
import numpy as np
from collections import defaultdict
from functools import reduce

s = input()
# n = int(input())
# A = list(map(int, input().split()))
# a, b = map(int, input().split())

# print((n-2)*180)

if 15 - len(s) + s.count('o') >= 8:
  print('YES')
else:
  print('NO')
Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict

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

keys = set()

def factorize(n):
    fct = defaultdict(int)
    b, e = 2, 0
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct[b] = e
        b, e = b + 1, 0
    if n > 1:
        fct[n] = 1

    for k, v in fct.items():
        keys.add(k)
    return fct
list(map(factorize, A))


max_factors = defaultdict(list)

def factorize2(n):
    fct = {}
    b, e = 2, 0
    for b in keys:
        while n % b == 0:
            n = n // b
            e = e + 1
        fct[b] = e
        max_factors[b].append(e)
        max_factors[b] = sorted(max_factors[b])[:2]
        b, e = b + 1, 0
    return fct
fcts = list(map(factorize2, A))

_res = 1

def it(fct):
    res = 1
    for k, ar in max_factors.items():

        if ar[0] == fct[k]:
            if len(ar) > 1:
                res *= k**ar[1]
        else:
            res *= k**ar[0]
    return res

print(max(it(fct) for fct in fcts))


Fixed submission:
import numpy as np
from fractions import gcd

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


L = np.zeros(N, dtype=int)
R = np.zeros(N, dtype=int)

L[0] = A[0]


# L[i] .. A[0], A[1], A[i] の最大公約数
R[N-1] = A[N-1]
# R[i] .. A[-1], A[-2], .. A[(-(i+1)] の最大公約数
# R[i] .. A[N-1], A[N-2], .. A[(N-i-1)] の最大公約数

for i in range(1, N):
    L[i] = gcd(A[i], L[i-1])

for i in range(N-2, -1, -1):
    R[i] = gcd(A[i], R[i+1])

def it(i):
    if i == 0:
        return R[1]
    if i == N-1:
        return L[N-2]
    return gcd(L[i-1], R[i+1])

# print(A)
# print(L)
# print(R)

print(max(it(i) for i in range(N)))
Buggy python submission (verdict: Time Limit Exceeded):
# from math import gcd
from fractions import gcd

def lcm(x, y):
    return (x * y) // gcd(x, y)


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

if N > M:
  N, M = M, N
  S, T = T, S

i = 0

while True:
  i += 1
  L = i*lcm(N, M)
  N_list = [(L//N)*k + 1 for k in range(N)]
  M_list = [(L//M)*k + 1 for k in range(M)]

  memo = {}

  for idx, n in enumerate(N_list):
    memo[n] = S[idx]

  for idx, m in enumerate(M_list):
    if m in memo.keys():
      if memo[m] != T[idx]:
        break
  else:
    print(L)
    exit(0)

  if L == N*M:
    break

print(-1)


Fixed submission:
# from math import gcd
from fractions import gcd

def lcm(x, y):
    return (x * y) // gcd(x, y)


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

if N > M:
  N, M = M, N
  S, T = T, S

i = 0

while True:
  i += 1
  L = i*lcm(N, M)
  N_list = [(L//N)*k + 1 for k in range(N)]
  M_list = [(L//M)*k + 1 for k in range(M)]

  # print(N_list)
  # print(M_list)

  memo = {}

  for idx, n in enumerate(N_list):
    memo[n] = S[idx]

  for idx, m in enumerate(M_list):
    if m in memo.keys():
      if memo[m] != T[idx]:
        break
  else:
    print(L)
    exit(0)

  # if L == N*M:
  break

print(-1)

Buggy python submission (verdict: Runtime Error):
# from math import gcd
from fraction import gcd

def lcm(x, y):
    return (x * y) // gcd(x, y)


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

if N > M:
  N, M = M, N
  S, T = T, S

i = 0

while True:
  i += 1
  L = i*lcm(N, M)
  N_list = [(L//N)*k + 1 for k in range(N)]
  M_list = [(L//M)*k + 1 for k in range(M)]

  memo = {}

  for idx, n in enumerate(N_list):
    memo[n] = S[idx]

  for idx, m in enumerate(M_list):
    if m in memo.keys():
      if memo[m] != T[idx]:
        break
  else:
    print(L)
    exit(0)

  if L == N*M:
    break

print(-1)


Fixed submission:
# from math import gcd
from fractions import gcd

def lcm(x, y):
    return (x * y) // gcd(x, y)


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

if N > M:
  N, M = M, N
  S, T = T, S

i = 0

while True:
  i += 1
  L = i*lcm(N, M)
  N_list = [(L//N)*k + 1 for k in range(N)]
  M_list = [(L//M)*k + 1 for k in range(M)]

  # print(N_list)
  # print(M_list)

  memo = {}

  for idx, n in enumerate(N_list):
    memo[n] = S[idx]

  for idx, m in enumerate(M_list):
    if m in memo.keys():
      if memo[m] != T[idx]:
        break
  else:
    print(L)
    exit(0)

  # if L == N*M:
  break

print(-1)
Buggy python submission (verdict: Runtime Error):
S = input()

K = int(input()) - 1

for i in range(K):
  if not S[i] == '1':
    print(S[i])
    exit()
else:
  print(S[i])


Fixed submission:
S = input()

K = int(input())

for i in range(K):
  if not S[i] == '1':
    print(S[i])
    exit()
else:
  print('1')
Buggy python submission (verdict: Time Limit Exceeded):
from functools import reduce

n = int(input())

res = []

while True:
  if n == 1:
    res.append(1)
    break
  if n%2 == 0:
    res.append(0)
    n //= -2
  else:
    res.append(1)
    n = (n-1)//(-2)


print(reduce(lambda s, x: s + str(x), reversed(res) ,""))


Fixed submission:
from functools import reduce

n = int(input())

if n == 0:
  print(0)
  exit()

res = []

while True:
  if n == 0:
    break
  if n == 1:
    res.append(1)
    break
  if n%2 == 0:
    res.append(0)
    n //= -2
  else:
    res.append(1)
    n = (n-1)//(-2)


print(reduce(lambda s, x: s + str(x), reversed(res) ,""))