Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
S = input()
Q = int(input())
ans = S
turncnt = 0
for i in range(Q):
    query = input().split()
    if (query[0] == "1"):
        turncnt = turncnt + 1
    if (query[0] == "2"):
        if (query[1] == "1"):
            if (turncnt % 2 == 0):
                ans = query[2] + ans
            else:
                ans = ans + query[2]
        if (query[1] == "2"):
            if (turncnt % 2 == 0):
                ans = ans + query[2]
            else:
                ans = query[2] + ans

if (turncnt % 2 == 1):
    ans = ans[::-1]    
print(ans)

Fixed submission:
from collections import deque

S = input()
Q = int(input())
ans = deque()
ans.append(S)
turncnt = 0
for i in range(Q):
    query = input().split()
    if (query[0] == "1"):
        turncnt = turncnt + 1
    if (query[0] == "2"):
        if (query[1] == "1"):
            if (turncnt % 2 == 0):
                ans.appendleft(query[2])
            else:
                ans.append(query[2])
        if (query[1] == "2"):
            if (turncnt % 2 == 0):
                ans.append(query[2])
            else:
                ans.appendleft(query[2])

anstr = "".join(ans)
if (turncnt % 2 == 1):
    anstr = anstr[::-1]
print(anstr)

Buggy python submission (verdict: Time Limit Exceeded):
S = input()
Q = int(input())
ans = S
for i in range(Q):
    query = input().split()
    if (query[0] == "1"):
        ans = ans[::-1]
    if (query[0] == "2"):
        if (query[1] == "1"):
            ans = query[2] + ans
        if (query[1] == "2"):
            ans = ans + query[2]

print(ans)

Fixed submission:
from collections import deque

S = input()
Q = int(input())
ans = deque()
ans.append(S)
turncnt = 0
for i in range(Q):
    query = input().split()
    if (query[0] == "1"):
        turncnt = turncnt + 1
    if (query[0] == "2"):
        if (query[1] == "1"):
            if (turncnt % 2 == 0):
                ans.appendleft(query[2])
            else:
                ans.append(query[2])
        if (query[1] == "2"):
            if (turncnt % 2 == 0):
                ans.append(query[2])
            else:
                ans.appendleft(query[2])

anstr = "".join(ans)
if (turncnt % 2 == 1):
    anstr = anstr[::-1]
print(anstr)
Buggy python submission (verdict: Runtime Error):
N,M = map(int,input().split())
sc = [[0,0]]*M
ans = [0]*N
f = True
ans = -1
for i in range(M):
    sc[i] = list(map(int,input().split()))

for i in range(1000):
    str_i = str(i)
    if (len(str_i) == N):
        f = True
        for j in range(M):
            f &= (str_i[sc[i][0]-1] == str(sc[i][1]))
        if (f):
            ans = i
            break

print(ans)

Fixed submission:
N,M = map(int,input().split())
sc = [[0,0]]*M
ans = [0]*N
f = True
ans = -1
for i in range(M):
    sc[i] = list(map(int,input().split()))

for i in range(1000):
    str_i = list(str(i))
    if (len(str_i) == N):
        f = True
        for j in range(M):
            f &= (str_i[sc[j][0]-1] == str(sc[j][1]))
        if (f):
            ans = i
            break

print(ans)

Buggy python submission (verdict: Runtime Error):
N,M = map(int,input().split())
sc = [[0,0]]*M
ans = [0]*N
f = True
for i in range(M):
    sc[i] = list(map(int,input().split()))

for i in range(M):
    ans[sc[i][0]-1] = str(sc[i][1])

sc.sort()
for i in range(M-1):
    if (sc[i][0] == sc[i+1][0]):
        if (sc[i][1] != sc[i+1][1]):
            f = False

if (f):
    for i in range(M):
        ans[i] = str(ans[i])

    if (ans[0] == "0"):
        if (N == 1):
            print(0)
        else:
            print(-1)
    else:
        print("".join(ans))
else:
    print(-1)

Fixed submission:
N,M = map(int,input().split())
sc = [[0,0]]*M
ans = [0]*N
f = True
ans = -1
for i in range(M):
    sc[i] = list(map(int,input().split()))

for i in range(1000):
    str_i = list(str(i))
    if (len(str_i) == N):
        f = True
        for j in range(M):
            f &= (str_i[sc[j][0]-1] == str(sc[j][1]))
        if (f):
            ans = i
            break

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n,a,b = map(int,input().split())

def modComb(n,r,mod):
    tmp = 1
    for i in range(1,r+1):
        tmp *= (n-i+1) % mod
        tmp *= pow(i,mod-2,mod)
    
    return tmp % mod


mod = 10**9+7
ans = pow(2,n,mod) - 1
ans %= mod

print(ans-modComb(n,a,mod)-modComb(n,b,mod) % mod)



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

def modComb(n,r,mod):
    tmp = 1
    r = min(r,n-r)
    for i in range(1,r+1):
        tmp = tmp * (n-i+1) % mod
        tmp = tmp * pow(i,mod-2,mod)
    
    return tmp % mod


mod = 10**9+7
ans = pow(2,n,mod) - 1

print((ans-modComb(n,a,mod)-modComb(n,b,mod)) % mod)
Buggy python submission (verdict: Time Limit Exceeded):
h, n = map(int, input().split())
a = [0] * n
b = [0] * n
for i in range(n):
    a[i], b[i] = map(int, input().split())

a_max = max(a)
# dp[i] : モンスターのHPをi減らすのに必要な魔力の最小値
dp = [0] * (h + a_max + 1)
dp[0] = 0

for i in range(1, h + a_max + 1):
    m = 10 ** 9
    for j in range(n):
        tmp = dp[i - a[j]] + b[j]
        if (m > tmp):
            m = tmp

    dp[i] = m

print(min(dp[h:]))


Fixed submission:
h, n = map(int, input().split())
a = [0] * n
b = [0] * n
for i in range(n):
    a[i], b[i] = map(int, input().split())

a_max = max(a)
# dp[i] : モンスターのHPをi減らすのに必要な魔力の最小値
dp = [0] * (h + a_max + 1)
dp[0] = 0

for i in range(1, h + a_max + 1):
    m = 10 ** 9
    for j in range(n):
        tmp = dp[i - a[j]] + b[j]
        if (m > tmp):
            m = tmp

    dp[i] = m

print(min(dp[h:]))
Buggy python submission (verdict: Runtime Error):
N,K = map(int,input().split())
R,S,P = map(int,input().split())
T = input()

# 相手の手がkeyだった時に勝つと得られるポイント
score = {"s":R,"p":S,"r":P}
# K手前が同じ手だったフラグ
flag = [False for i in range(N)]
ans = 0
for i in range(N):
    if (flag[i]):
        s += "l"
    else:
        ans += score[T[i]]
        s += "w"
        if (N-i-1 >= K):
            if (T[i] == T[i+K]):
                flag[i+K] = True

print(ans)


Fixed submission:
N,K = map(int,input().split())
R,S,P = map(int,input().split())
T = input()

# 相手の手がkeyだった時に勝つと得られるポイント
score = {"s":R,"p":S,"r":P}
# K手前が同じ手だったフラグ
flag = [False for i in range(N)]
ans = 0
for i in range(N):
    if (flag[i]):
        pass
    else:
        ans += score[T[i]]
        if (N-i-1 >= K):
            if (T[i] == T[i+K]):
                flag[i+K] = True

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
s = input()

ans = 0

for i in range(1000):
    ss = str(i).zfill(3)
    idx = 0
    for j in range(len(s)):
        if (s[j] == ss[idx]):
            idx += 1
            if (idx == 3):
                break
    if (idx == 3):
        ans += 1

print(ans)

Fixed submission:
n = int(input())
s = input()

ans = 0

for i in range(1000):
    ss = str(i).zfill(3)
    if (ss[0] in s):
        ind1 = s.index(ss[0])
        if (ss[1] in s[ind1+1:]):
            ind2 = ind1+1 + s[ind1+1:].index(ss[1])
            if (ss[2] in s[ind2+1:]):
                ans += 1

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import itertools

n = int(input())
s = list(map(int,input()))

l = set(itertools.combinations(s,3))
print(len(l))


Fixed submission:
n = int(input())
s = input()

ans = 0

for i in range(1000):
    ss = str(i).zfill(3)
    if (ss[0] in s):
        ind1 = s.index(ss[0])
        if (ss[1] in s[ind1+1:]):
            ind2 = ind1+1 + s[ind1+1:].index(ss[1])
            if (ss[2] in s[ind2+1:]):
                ans += 1

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import itertools
n = int(input())
s = input()
l = set(list(itertools.combinations(s,3)))
print(len(l))


Fixed submission:
n = int(input())
s = input()

ans = 0

for i in range(1000):
    ss = str(i).zfill(3)
    if (ss[0] in s):
        ind1 = s.index(ss[0])
        if (ss[1] in s[ind1+1:]):
            ind2 = ind1+1 + s[ind1+1:].index(ss[1])
            if (ss[2] in s[ind2+1:]):
                ans += 1

print(ans)
Buggy python submission (verdict: Runtime Error):
n = int(input())
d = list(map(int,input().split()))
db = [0] * n
MOD = 998244353

#距離iの頂点の数をdb[i]に保存
for i in range(n):
    db[d[i]] += 1

#末尾に連続する0を削除
if (db[n-1] == 0):
    l = n-1
    for i in range(1,n):
        tmp = db[n-i]
        if (tmp == 0) : l = n-i 
        else : break
    
    del db[l:n]


if (d[0] != 0)|(db[0] != 1):
    print(0)
    exit()
if (len(db) <= 2):
    print(len(db)-1)
    exit()

db.append(1)
ans = 1

for i in range(len(db)-1):
    tmp = (db[i]**db[i+1]) % MOD
    ans *= tmp

print(ans)

Fixed submission:
n = int(input())
if (n % 2 == 0):print(n//2-1)
else : print(n//2)
Buggy python submission (verdict: Runtime Error):
# D Water_Bottle
import math
a,b,x = map(int,input().split(" "))
x /= a
if (x > a*b/2):
    #水筒の半分の容積より水の容積が大きかった場合
    ha = a/2
    print(90-math.degrees(math.atan(ha/(b-(x/a)))))
else:
    #水の容積が水筒の半分の容積以下だった場合
    c = 2*x/b
    print(90-math.degrees(math.atan(c/b)))



Fixed submission:
# D Water_Bottle
import math
a,b,x = map(int,input().split(" "))
x /= a
if (x == a*b):
    #水筒が満タンの場合
    print(0)
elif (x > a*b/2):
    #水筒の半分の容積より水の容積が大きかった場合
    ha = a/2
    print(90-math.degrees(math.atan(ha/(b-(x/a)))))
else:
    #水の容積が水筒の半分の容積以下だった場合
    c = 2*x/b
    print(90-math.degrees(math.atan(c/b)))
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
l = list(map(int, input().split()))

def meguru_nibutan(ar,m,key):
    a = m
    b = len(ar)
    while(abs(a-b) > 1):
        c = (a+b)//2
        if (ar[c] > key):
            a = c
        else:
            b = c
    return a

def main():
    cnt = 0
    l.sort(reverse=True)
    for a in range(0,n-2):
        for b in range(a+1,n-1):
            cnt += meguru_nibutan(l,b,l[a]-l[b]) - b
    print(cnt)

if (__name__ == "__main__"):
    main()

Fixed submission:
import bisect
n = int(input())
l = list(map(int, input().split()))

def meguru_nibutan(ar,m,key):
    a = m
    b = len(ar)
    while(abs(a-b) > 1):
        c = (a+b)//2
        if (ar[c] > key):
            a = c
        else:
            b = c
    return a

def main():
    cnt = 0
    l.sort()
    for a in range(0,n-2):
        for b in range(a+1,n-1):
            #cnt += meguru_nibutan(l,b,l[a]-l[b]) - b
            cnt += bisect.bisect_left(l,l[a]+l[b]) - 1 - b
    print(cnt)

if (__name__ == "__main__"):
    main()

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
l = [int(i) for i in input().split(" ")]

def meguru_nibutan(ar,m,key):
    a = m
    b = len(ar)
    while(abs(a-b) > 1):
        c = (a+b)//2
        if (ar[c] > key):
            a = c
        else:
            b = c
    return a

def main():
    cnt = 0
    l.sort(reverse=True)
    for a in range(0,n-2):
        for b in range(a+1,n-1):
            cnt += meguru_nibutan(l,b,l[a]-l[b]) - b
    print(cnt)

if (__name__ == "__main__"):
    main()

Fixed submission:
import bisect
n = int(input())
l = list(map(int, input().split()))

def meguru_nibutan(ar,m,key):
    a = m
    b = len(ar)
    while(abs(a-b) > 1):
        c = (a+b)//2
        if (ar[c] > key):
            a = c
        else:
            b = c
    return a

def main():
    cnt = 0
    l.sort()
    for a in range(0,n-2):
        for b in range(a+1,n-1):
            #cnt += meguru_nibutan(l,b,l[a]-l[b]) - b
            cnt += bisect.bisect_left(l,l[a]+l[b]) - 1 - b
    print(cnt)

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

a,b = map(int,input().split())

g = math.gcd(a,b)
ans = 0
sqrtg = math.ceil(math.sqrt(g))+1
for i in range(2,sqrtg):
    #割り切れるなら割り切れなくなるまでiで割り続ける
    if ((g // i * i == g)):
        ans += 1
        while (g // i * i == g):
            g //= i

print(ans+1)





Fixed submission:
import fractions
import math

a,b = map(int,input().split())

g = fractions.gcd(a,b)
ans = 0
sqrtg = math.ceil(math.sqrt(g))
for i in range(2,sqrtg):
    #割り切れるなら割り切れなくなるまでiで割り続ける
    if (g%i == 0):
        ans += 1
        while (g % i == 0):
            g //= i
            
if (g != 1):
    ans += 1
print(ans+1)
Buggy python submission (verdict: Time Limit Exceeded):
import math

def log2(x):
    return math.log10(x)/math.log10(2)

N,M = map(int,input().split())
A = [0]*N
A = list(map(int,input().split()))
if (N == 1):
    print(A[0]//(2**M))
else:
    while (M != 0):
        A.sort(reverse=True)
        y = min(math.floor(log2(A[0]/A[1])+1),M)
        A[0] //= 2**y
        M -= y

    print(sum(A))


Fixed submission:
import math
import heapq

N,M = map(int,input().split())
A = [0]*N
A = list(map(lambda x: int(x)*(-1),input().split()))
if (N == 1):
    print((-1 * A[0])//(2**M))
else:
    """
    while (M != 0):
        A.sort(reverse=True)
        y = min(math.floor(log2(A[0]/A[1])+1),M)
        A[0] //= 2**y
        M -= y
    """
    """
    A.sort(reverse=True)
    for i in range(N):
        y = min(A[i] // 2,M)
        A[i] //= 2**y
        M -= y
        if (M <= 0):
            break
    """
    heapq.heapify(A)

    for i in range(M):
        m = heapq.heappop(A) * -1
        heapq.heappush(A,(m//2 * -1))

    print(-sum(A))

Buggy python submission (verdict: Runtime Error):
import math

N,M = map(int,input().split())
A = [0]*N
A = list(map(int,input().split()))
if (N == 1):
    print(A[0]//(2**M))
else:
    while (M != 0):
        A.sort(reverse=True)
        y = min(math.floor(math.log2(A[0]/A[1])+1),M)
        A[0] //= 2**y
        M -= y

    print(sum(A))


Fixed submission:
import math
import heapq

N,M = map(int,input().split())
A = [0]*N
A = list(map(lambda x: int(x)*(-1),input().split()))
if (N == 1):
    print((-1 * A[0])//(2**M))
else:
    """
    while (M != 0):
        A.sort(reverse=True)
        y = min(math.floor(log2(A[0]/A[1])+1),M)
        A[0] //= 2**y
        M -= y
    """
    """
    A.sort(reverse=True)
    for i in range(N):
        y = min(A[i] // 2,M)
        A[i] //= 2**y
        M -= y
        if (M <= 0):
            break
    """
    heapq.heapify(A)

    for i in range(M):
        m = heapq.heappop(A) * -1
        heapq.heappush(A,(m//2 * -1))

    print(-sum(A))

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

N,M = map(int,input().split())
A = [0]*N
A = list(map(int,input().split()))
if (N == 1):
    print(A[0]//(2**M))
else:
    while (M != 0):
        A.sort(reverse=True)
        y = min(math.floor(math.log2(A[0]/A[1])+1),M)
        A[0] //= 2**y
        M -= y

    print(sum(A))


Fixed submission:
import math
import heapq

N,M = map(int,input().split())
A = [0]*N
A = list(map(lambda x: int(x)*(-1),input().split()))
if (N == 1):
    print((-1 * A[0])//(2**M))
else:
    """
    while (M != 0):
        A.sort(reverse=True)
        y = min(math.floor(log2(A[0]/A[1])+1),M)
        A[0] //= 2**y
        M -= y
    """
    """
    A.sort(reverse=True)
    for i in range(N):
        y = min(A[i] // 2,M)
        A[i] //= 2**y
        M -= y
        if (M <= 0):
            break
    """
    heapq.heapify(A)

    for i in range(M):
        m = heapq.heappop(A) * -1
        heapq.heappush(A,(m//2 * -1))

    print(-sum(A))
Buggy python submission (verdict: Time Limit Exceeded):
# C Green_Bin
n = int(input())
sl = []
ans = 0
for i in range(n):
    s = "".join(sorted(input()))
    for j in range(i):
        if (sl[j] == s):
            ans += 1
    sl.append(s)

print(ans)


Fixed submission:
# C Green_Bin
n = int(input())
sl = []
ans = 0
for i in range(n):
    s = "".join(sorted(input()))
    sl.append(s)
sl.sort()
bi = ""
tmp = 0
for i in sl:
    if (bi == i):
        tmp += 1
    else:
        ans += (tmp+1)*(tmp)//2
        tmp = 0
    bi = i
ans += (tmp+1)*(tmp)//2

print(ans)
Buggy python submission (verdict: Runtime Error):
from math import gcd
a = list(map(int,input().split()))

def fun(x,c,d):
    return x - div(x,c) - div(x,d) + div(x,c*d//gcd(c,d))

def div(a,b):
    return a // b

print(fun(a[1],a[2],a[3])-fun(a[0]-1,a[2],a[3]))

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

def fun(x,c,d):
    return x - div(x,c) - div(x,d) + div(x,c*d//gcd(c,d))

def div(a,b):
    return a // b

print(fun(a[1],a[2],a[3])-fun(a[0]-1,a[2],a[3]))
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
pos = []
for _ in range(n):
    p = list(map(int, input().split()))
    pos.append(p)

ans = 0
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        dpos = [pos[i][0] - pos[j][0], pos[i][1] - pos[j][1]]
        cnt = 0
        for k in range(n):
            for l in range(n):
                if k == l:
                    continue
                tmp = [pos[k][0] - pos[l][0], pos[k][1] - pos[l][1]]
                if dpos[0] == tmp[0] and dpos[1] == tmp[1]:
                    cnt += 1
        ans = max(cnt, ans)

print(n-ans)


Fixed submission:
n = int(input())
pos = []
for _ in range(n):
    p = list(map(int, input().split()))
    pos.append(p)

ans = 0
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        dpos = [pos[i][0] - pos[j][0], pos[i][1] - pos[j][1]]
        cnt = 0
        for k in range(n):
            for l in range(n):
                if k == l:
                    continue
                tmp = [pos[k][0] - pos[l][0], pos[k][1] - pos[l][1]]
                if dpos[0] == tmp[0] and dpos[1] == tmp[1]:
                    cnt += 1
        ans = max(cnt, ans)

print(n-ans)
Buggy python submission (verdict: Time Limit Exceeded):
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]

U = [[0 for _ in range(w)] for _ in range(h)]
D = [[0 for _ in range(w)] for _ in range(h)]
L = [[0 for _ in range(w)] for _ in range(h)]
R = [[0 for _ in range(w)] for _ in range(h)]

for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            U[i][j] = 0
            L[i][j] = 0
        else:
            if i == 0:
                U[i][j] = 1
            else:
                U[i][j] = U[i - 1][j] + 1
            if j == 0:
                L[i][j] = 1
            else:
                L[i][j] = L[i][j - 1] + 1


for i in reversed(range(h)):
    for j in reversed(range(w)):
        if s[i][j] == "#":
            D[i][j] = 0
            R[i][j] = 0
        else:
            if i == h-1:
                D[i][j] = 1
            else:
                D[i][j] = D[i + 1][j] + 1
            if j == w-1:
                R[i][j] = 1
            else:
                R[i][j] = R[i][j + 1] + 1

ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, U[i][j] + D[i][j] + L[i][j] + R[i][j] - 3)

print(ans)

Fixed submission:
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]

U = [[0 for _ in range(w)] for _ in range(h)]
D = [[0 for _ in range(w)] for _ in range(h)]
L = [[0 for _ in range(w)] for _ in range(h)]
R = [[0 for _ in range(w)] for _ in range(h)]

for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            U[i][j] = 0
            L[i][j] = 0
        else:
            if i == 0:
                U[i][j] = 1
            else:
                U[i][j] = U[i - 1][j] + 1
            if j == 0:
                L[i][j] = 1
            else:
                L[i][j] = L[i][j - 1] + 1


for i in reversed(range(h)):
    for j in reversed(range(w)):
        if s[i][j] == "#":
            D[i][j] = 0
            R[i][j] = 0
        else:
            if i == h-1:
                D[i][j] = 1
            else:
                D[i][j] = D[i + 1][j] + 1
            if j == w-1:
                R[i][j] = 1
            else:
                R[i][j] = R[i][j + 1] + 1

ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, U[i][j] + D[i][j] + L[i][j] + R[i][j] - 3)

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys

sys.setrecursionlimit(2*10**9)

def main():
    N = int(input())
    A = sorted(input().split(" "))
    ans = [0]*N
    for i in range(N):
        tmp = A[i]
        if (i == N-1):
            A[i] = A[N-2]
        else :
            A[i] = A[N-1]
        ans.append(recursive_gcd(N,A))
        A[i] = tmp
    print(max(ans))


def recursive_gcd(n,array):
    if (n <= 2):
        return gcd_euclid(int(array[0]),int(array[1]))
    else:
        return gcd_euclid(recursive_gcd(n-1,array),int(array[n-1]))

# http://d.hatena.ne.jp/sh-2/20100320/1269039543 から引用
def gcd_euclid(u, v) :
  while (0 != v) :
    r = u % v
    u = v
    v = r
  return u
#引用ここまで

if __name__ == "__main__":
    main()

Fixed submission:
from fractions import gcd as m_gcd

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


def gcd(a, b):
    if a == 0 or b == 0:
        return max(a, b)
    return m_gcd(a, b)


l = [0] * (n + 2)
r = [0] * (n + 2)
ans = [0] * n

for i in range(1, n+1):
    l[i] = gcd(l[i - 1], a[i - 1])
    r[n - i + 1] = gcd(r[n - i + 2], a[n - i])

for i in range(1, n + 1):
    ans[i-1] = gcd(l[i-1], r[i+1])

print(max(ans))

Buggy python submission (verdict: Runtime Error):
def main():
    N = int(input())
    A = sorted(input().split(" "))
    ans = [0]*N
    for i in range(N):
        tmp = A[i]
        if (i == N-1):
            A[i] = A[N-2]
        else :
            A[i] = A[N-1]
        ans.append(recursive_gcd(N,A))
        A[i] = tmp
    print(max(ans))


def recursive_gcd(n,array):
    if (n <= 2):
        return gcd_euclid(int(array[0]),int(array[1]))
    else:
        return gcd_euclid(recursive_gcd(n-1,array),int(array[n-1]))

# http://d.hatena.ne.jp/sh-2/20100320/1269039543 から引用
def gcd_euclid(u, v) :
  while (0 != v) :
    r = u % v
    u = v
    v = r
  return u
#引用ここまで

if __name__ == "__main__":
    main()

Fixed submission:
from fractions import gcd as m_gcd

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


def gcd(a, b):
    if a == 0 or b == 0:
        return max(a, b)
    return m_gcd(a, b)


l = [0] * (n + 2)
r = [0] * (n + 2)
ans = [0] * n

for i in range(1, n+1):
    l[i] = gcd(l[i - 1], a[i - 1])
    r[n - i + 1] = gcd(r[n - i + 2], a[n - i])

for i in range(1, n + 1):
    ans[i-1] = gcd(l[i-1], r[i+1])

print(max(ans))
Buggy python submission (verdict: Time Limit Exceeded):
tmp = input()
L = int(tmp.split(" ")[0])
Q = int(tmp.split(" ")[1])
S = input()
ans = []
preans = 0

for i in range(Q) :
    tmp = input()
    left = int(tmp.split(" ")[0])
    right = int(tmp.split(" ")[1])
    for j in range(left-1,right-1) :
        test = S[j:j+2]
        if test == "AC":
            preans += 1
    ans.append(preans)
    preans = 0

for i in range(Q) :
    print(str(ans[i]))

Fixed submission:
n, q = map(int, input().split())
s = list(input())
ls = len(s)
for i in range(0, ls):
    if (s[i] == "A"):
        if (i != ls-1)and(s[i + 1] == "C"):
            s[i] = "a"

anum = [0]
for i in range(1, ls):
    if (s[i - 1] == "a"):
        anum.append(anum[i - 1] + 1)
    else:
        anum.append(anum[i - 1])

for i in range(q):
    l, r = map(int, input().split())
    print(anum[r-1]-anum[l-1])
Buggy python submission (verdict: Runtime Error):
s = input()
key = "keyence"
ptr = 0

for c in s:
    if c == key[ptr]:
        ptr += 1

print("YES" if ptr == 7 else "NO")


Fixed submission:
s = list(input())
ls = len(s)
key = "keyence"
if "".join(s) == key:
    print("YES")
    exit()
f = False
for l in range(ls):
    for r in range(l + 1, ls):
        f |= "".join(["".join(s[:l]), "".join(s[r:])]) == key

print("YES" if f else "NO")
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
h = list(map(int, input().split()))


def cost(x: int, y: int) -> int:
    global h
    return abs(h[x] - h[y])


dp = [10**9] * n
dp[0] = 0

for i in range(1, n):
    for j in range(k):
        d = i - j - 1
        if d < 0 or d > n:
            break
        dp[i] = min(dp[i], dp[d] + cost(i, d))
print(dp[n-1])


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


def cost(x: int, y: int) -> int:
    global h
    return abs(h[x] - h[y])


dp = [10**9] * n
dp[0] = 0

for i in range(1, n):
    for j in range(k):
        d = i - j - 1
        if d < 0 or d > n:
            break
        dp[i] = min(dp[i], dp[d] + cost(i, d))
print(dp[n-1])