Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
n,k = map(int,input().split())
s = input()
#入力
cnt = 0
if s[0] == '0':
    cnt += 1
for i in range(1,n):
    if s[i-1] == '1' and s[i] == '0':
        cnt += 1
##切り替わるところで＋1
if cnt <= k:
    print(n)
    #切り替わるところが動かす回数より少ない場合n(自明)
else:
    one_left,one_right = [0],[]
    #
    for i in range(1,n):
        if s[i-1] == '0' and s[i] == '1':
            one_left.append(i)
        if s[i-1] == '1' and s[i] == '0':
            one_right.append(i)
    #01 の時右に加える10の時左に加える
    #切り替えの時の配列の番号を加える
    one_right.append(n)
    #nはとりあえず右
    if s[0] == '1':
        one_right.pop(0)
    if s[-1] == '1':
        one_left.pop(-1)
    #最初の人が逆立ちしているなら右の切り替えの最初はなし
    #最後の人が逆立ちしているなら左の切り替えの最後はなし
    #print(one_right,'r')
    #print(one_left,'l')

    ans = 0
    #ans 01,10の切り替えの少ないほうでloopを回す
    for i in range(min(len(one_left),len(one_right)-k+1)):
        ans = max(ans,one_right[i+k-1]-one_left[i])
        #ans は　ある点までの個数-フラグの開始点までの個数の最大値
print(ans)



Fixed submission:
#looked ans

n,k = map(int,input().split())
s = input()
#入力
cnt = 0
if s[0] == '0':
    cnt += 1
for i in range(1,n):
    if s[i-1] == '1' and s[i] == '0':
        cnt += 1
##切り替わるところで＋1
if cnt <= k:
    print(n)
    #切り替わるところが動かす回数より少ない場合n(自明)
else:
    one_left,one_right = [0],[]
    #
    for i in range(1,n):
        if s[i-1] == '0' and s[i] == '1':
            one_left.append(i)
        if s[i-1] == '1' and s[i] == '0':
            one_right.append(i)
    #01 の時右に加える10の時左に加える
    #切り替えの時の配列の番号を加える
    one_right.append(n)
    #nはとりあえず右
    if s[0] == '1':
        one_right.pop(0)
    if s[-1] == '1':
        one_left.pop(-1)
    #最初の人が逆立ちしているなら右の切り替えの最初はなし
    #最後の人が逆立ちしているなら左の切り替えの最後はなし
    #print(one_right,'r')
    #print(one_left,'l')

    ans = 0
    #ans 01,10の切り替えの少ないほうでloopを回す
    for i in range(min(len(one_left),len(one_right)-k+1)):
        ans = max(ans,one_right[i+k-1]-one_left[i])
        #ans は　ある点までの個数-フラグの開始点までの個数の最大値
    print(ans)
Buggy python submission (verdict: Runtime Error):
S = input()
ans = 0
ans_lis = []
for x in S:
    if x == 'A' or x == 'C'or x == 'G' or x == 'T':
        ans += 1
    else:
        ans_lis.append(ans)
        ans = 0
print(max(ans_lis))



Fixed submission:
S = input()
ans = 0
ans_lis = [0]
for x in S:
    if x == 'A' or x == 'C' or x == 'G' or x == 'T':
        ans += 1
    else:
        ans_lis.append(ans)
        ans = 0
ans_lis.append(ans)
print(max(ans_lis))
Buggy python submission (verdict: Time Limit Exceeded):
def is_unq(seq):
    return len(seq) == len(set(seq))

from itertools import combinations as cmb
n = int(input())
S = input()
Sli = list(S)
ans_s = [[] for _ in range(1,n+1)]
ans = 0
for x in range(n):
    lis = list(cmb(Sli,x+1))
    ans_s[x] += lis
    for y in range(len(ans_s[x])):
        flag = 0
        if is_unq(ans_s[x][y]) == True:
            ans += 1
print(ans)

Fixed submission:
N = int(input())
S = input()
d = {}
mod = 10**9 + 7
for key in S:
    if key in d:
        d[key] += 1
    else:
        d[key] = 1
ans = 1
for x in d.values():
    ans *= x+1
print(ans % mod -1)
Buggy python submission (verdict: Time Limit Exceeded):
A,B = map(int,input().split())
ans = A
for _ in range(A+1,B+1):
    ans = ans^_
print(ans)

Fixed submission:
def calcF(n):
    if n%2 == 0:
        if n%4 == 0:
            return n
        else:
            return n^1
    else:
        if (n+1)%4 == 0:
            return 0
        else:
            return 1
A,B = map(int,input().split())
ans_A = calcF(A-1)
#print(ans_A)
ans_B = calcF(B)
#print(ans_B)
ans = ans_A^ans_B
print(ans)
Buggy python submission (verdict: Runtime Error):
a,b,c = map(int,input().split("/"))
if a >=2019 && b >= 5:
    print('TBD')
else:
    print('Heisei')

Fixed submission:
a,b,c = map(int,input().split("/"))
if a >=2019 and b >= 5:
    print('TBD')
else:
    print('Heisei')
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = list(map(int,input().split()))
while len(A) > 1:
    a_ = A[0]
    for x in range(1,len(A)):
        A[x] %= a_
    A = [ans for ans in A if ans > 0]
    A.sort()
print(A[0])

Fixed submission:
a,b = map(int,input().split())
if b%a == 0:
    print(a+b)
else:
    print(b-a)

Buggy python submission (verdict: Runtime Error):
N = int(input())
A = list(map(int,input().split()))
for main_loop in range (0,N):    
    A.sort()
    de = A.count(0)
    del A[:de]
    li = len(A)
    if A[0] == 1:
        break
    for x in range(1,li):
        A[x] = A[x]%A[0]
print(A[0])


Fixed submission:
a,b = map(int,input().split())
if b%a == 0:
    print(a+b)
else:
    print(b-a)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
Flag = [0 for i in range(N)]
A = list(map(int,input().split()))
while len(A) != 1:
    A.sort()
    mi = min(A)
    for _ in range(1,len(A)):
        if A.count(1) > 1:
            del A[1:]
            break
        try:
            A[_] -= mi
            if A[_] <= 0:
                A.pop(_)
        except:
            pass
print(A[0])

Fixed submission:
N = int(input())
A = list(map(int,input().split()))
while len(A) > 1:
    a_ = A[0]
    for x in range(1,len(A)):
        A[x] %= a_
    A = [ans for ans in A if ans > 0]
    A.sort()
print(A[0])
Buggy python submission (verdict: Runtime Error):
c,a,b = map(int,inpput().split())

print(c*a/2)

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

print(int((c*a)/2))
Buggy python submission (verdict: Runtime Error):
N,K = map(int,input().split())
lis = [int(input()) for x in range(N)]
lis.sort()
print(min(lis[i+K-1] - lis[i] for x in range(N-K+1)))

Fixed submission:
N,K = map(int,input().split())
lis = [int(input()) for x in range(N)]
lis.sort()
print(min(lis[i+K-1] - lis[i] for i in range(N-K+1)))
Buggy python submission (verdict: Runtime Error):
a = list(map(int,input()))
a.sort(reverse=True)
print(int(str(a[0])+str(a[1])) + a[2])

Fixed submission:
a = list(map(int,input().split()))
a.sort(reverse=True)
print(int(str(a[0])+str(a[1])) + a[2])
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
lis = sorted(list(map(int,input().split())))
now = -1
ans = 0
for x in range(n):
    if lis[x] == now:
        continue
    now = lis[x]
    val = 0
    for y in range(n-x):
        if lis[x]+2 >= lis[x+y]:
            val += 1
            ans = max(ans,val)

print(ans)


Fixed submission:
n = int(input())
lis = sorted(list(map(int,input().split())))
now = -1
ans = 0
for x in range(n):
    if lis[x] == now:
        continue
    now = lis[x]
    val = 0
    for y in range(n-x):
        if lis[x]+2 >= lis[x+y]:
            val += 1
            ans = max(ans,val)
        else:
            break

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
lis = sorted(list(map(int,input().split())))
now = -1
ans = 0
for x in range(n):
    if lis[x] == now:
        continue
    now = lis[x]
    val = 0
    for y in range(n-x):
        if lis[x]+2 >= lis[x+y]:
            val += 1
            ans = max(ans,val)

print(ans)


Fixed submission:
n = int(input())
lis = sorted(list(map(int,input().split())))
now = -1
ans = 0
for x in range(n):
    if lis[x] == now:
        continue
    now = lis[x]
    val = 0
    for y in range(n-x):
        if lis[x]+2 >= lis[x+y]:
            val += 1
            ans = max(ans,val)
        else:
            break

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
K,S = map(int,input().split())
ans = 0
for a in range(K+1):
    for b in range(K+1):
        for c in range(K+1):
            if S == a + b + c:
                ans += 1
print(ans)

Fixed submission:
K,S = map(int,input().split())
ans = 0
for a in range(K+1):
    for b in range(K+1):
        c = S - a - b
        if 0 <= c and c <= K:
            ans += 1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
my_list = list(map(int, input().split()))
ans = 0

for i in range(N - 1):
    for j in range(i + 1, N):
        if j - i == my_list[i] + my_list[j]:
            ans += 1
print(ans)

Fixed submission:
N = int(input())
my_list = list(map(int, input().split()))
my_dict1 = {}
my_dict2 = {}

# j - i == Aj + Ai
# j - Aj == Ai + i

#Ai + i
for i in range(N):
    key = my_list[i] + i
    if key in my_dict1.keys():
        my_dict1[key] += 1
    else:
        my_dict1[key] = 1

#j - Aj
for j in range(N):
    key = j - my_list[j]
    if key in my_dict2.keys():
        my_dict2[key] += 1
    else:
        my_dict2[key] = 1


ans = 0
for key in my_dict1.keys():
    if key in my_dict2.keys():
        ans += my_dict1[key] * my_dict2[key]

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
memo = {}

def func(i, j):
    if (i, j) in memo:
        return memo[(i, j)]

    count = 0
    for n in range(1, N+1):
        str_n = str(n)
        if str_n[-1] == str(i) and str_n[0] == str(j):
            count += 1
    
    memo[(i,j)] = count
    return count

ret = 0
for i in range(1, N+1):
    ret += func(str(i)[0], str(i)[-1])

print(ret)




Fixed submission:
N = int(input())
memo = {}

def func(i, j):
    if (i, j) in memo:
        return memo[(i, j)]

    count = 0
    n = 1
    while n <= N:
        str_n = str(n)

        if n >= 10 and str_n[0] != str(j):
            n += 10 ** (len(str_n) - 1)
            continue

        if str_n[-1] == str(i) and str_n[0] == str(j):
            count += 1
            n += 10
            continue

        n += 1
    
    memo[(i,j)] = count
    return count

ret = 0
for i in range(1, N+1):
    ret += func(str(i)[0], str(i)[-1])

print(ret)
Buggy python submission (verdict: Time Limit Exceeded):
import bisect

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

A_list = sorted(A_list)
#print(A_list)

for i in range(M):
    val = A_list.pop()//2
    bisect.insort_left(A_list, val, lo=min(N-1, max(0,(N-M) + i)) )

print(sum(A_list))

Fixed submission:
import heapq

N,M = map(int, input().split())
A_list = list(map(int, input().split()))
for i in range(N):
    A_list[i] *= -1

heapq.heapify(A_list)

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

print(sum(A_list) * -1)

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

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

A_list = sorted(A_list)
#print(A_list)

for i in range(M):
    val = A_list.pop()//2
    bisect.insort_left(A_list, val, lo=(N-M) + i )

print(sum(A_list))

Fixed submission:
import heapq

N,M = map(int, input().split())
A_list = list(map(int, input().split()))
for i in range(N):
    A_list[i] *= -1

heapq.heapify(A_list)

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

print(sum(A_list) * -1)

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

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

A_list = sorted(A_list)
#print(A_list)

for i in range(M):
    val = A_list.pop()//2
    bisect.insort_left(A_list, val)

print(sum(A_list))

Fixed submission:
import heapq

N,M = map(int, input().split())
A_list = list(map(int, input().split()))
for i in range(N):
    A_list[i] *= -1

heapq.heapify(A_list)

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

print(sum(A_list) * -1)
Buggy python submission (verdict: Runtime Error):
N,M = map(int, input().split())
a_b_list = []
for i in range(N):
    a,b = map(int, input().split())
    a_b_list.append([a,b])

a_b_list.sort(key=lambda x:(x[1],x[0]))
a_b_list.reverse()
#print(a_b_list)
task_list = [0] * (M+1)


for a,b in a_b_list:
#    print(a, b)
    if task_list[a] == 0:
#        print("append")
        task_list[a] = b
    else:
#        print("NOT append")
        index = a + 1
        while index <= M:
            if task_list[index] == 0:
                task_list[index] = b
                break
            index += 1
print(sum(task_list))
#print(task_list)

Fixed submission:
import heapq

N,M = map(int, input().split())
a_b_list = []
for i in range(N):
    a,b = map(int, input().split())
    a_b_list.append([a,b])

a_b_list.sort()
task_list = [0] * (M+1)

heap = []
index = 0
for day in range(1, M+1):
    while index < N:
        if a_b_list[index][0] == day:
            heapq.heappush(heap, a_b_list[index][1] * -1)
            index += 1
        else:
            break
    if len(heap) != 0:
        task_list[day] = heapq.heappop(heap)

#print(task_list)
print(sum(task_list) * -1)


# for a,b in a_b_list:
# #    print(a, b)
#     if task_list[a] == 0:
# #        print("append")
#         task_list[a] = b
#     else:
# #        print("NOT append")
#         index = a + 1
#         while index <= M:
#             if task_list[index] == 0:
#                 task_list[index] = b
#                 break
#             index += 1
# print(sum(task_list))
# #print(task_list)
Buggy python submission (verdict: Runtime Error):
N = int(input())
d_list = list(map(int, input().split()))
d_list.sort()

n1 = d_list[N//2]
print(d_list[n1 + 1] - d_list[n1])

              

Fixed submission:
N = int(input())
d_list = list(map(int, input().split()))
d_list.sort()

n1 = N//2
print(d_list[n1] - d_list[n1 - 1])
Buggy python submission (verdict: Runtime Error):
S = input()
ret = ""
for i in range(len(S)):
    if i == K-1:
        ret += S[i].lower()
    else:
        ret += S[i]
print(ret)

Fixed submission:
N,K = map(int, input().split())
S = input()
ret = ""
for i in range(len(S)):
    if i == K-1:
        ret += S[i].lower()
    else:
        ret += S[i]
print(ret)
Buggy python submission (verdict: Runtime Error):
s = input("")
s1 = s[0:(n-1)/2]
s2 = s[(n+3)/2-1:]

if (s1 == s1[::-1] and s2 == s2[::-1]):
	print("Yes")
else:
  	print("No")
    

Fixed submission:
s = input('')
n = len(s)
s1 = s[0:(n-1)//2]
s2 = s[(n+3)//2-1:]

if (s == s[::-1] and s1 == s1[::-1] and s2 == s2[::-1]):
	print("Yes")
else:
  	print("No")
Buggy python submission (verdict: Runtime Error):
h, w = map(int, input("").split(''))

print(ceil(w/2) * ceil(h/2) * (floor(w/2) * floor(h/2))

Fixed submission:
from math import *
h, w = map(int, input('').split(' '))

if h > 1 and w > 1:
	print(ceil(w/2) * ceil(h/2) + floor(w/2) * floor(h/2) )
else:
  print(1)
Buggy python submission (verdict: Time Limit Exceeded):
"""
i - j = A[i] + A[j]
-> i - A[i] = j + A[j]
i > j
"""
N = int(input())
high = list(map(int, input().split()))

cnt = 0
calc = []
for i in range(1, N+1):
  tmp = i - high[i-1]
  calc.append(i + high[i-1])
  if tmp in calc[:-1]:
    cnt += calc[:-1].count(tmp)

print(cnt)

Fixed submission:
"""
i - j = A[i] + A[j]
> i - A[i] = j + A[j]
i > j
"""
N = int(input())
high = list(map(int, input().split()))

ans = 0
calc = {}
for i in range(1, N+1):
  try:
    ans += calc[i - high[i-1]]
  except KeyError:
    pass
  if (i + high[i-1]) in calc.keys():
    calc[i + high[i-1]] += 1
  else:
    calc[i + high[i-1]] = 1

print(ans)

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

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

cnt = 0

for tup in itertools.combinations(range(N), 2):
  if abs(tup[0]-tup[1]) == (high[tup[0]]+high[tup[1]]):
    cnt += 1

print(cnt)

Fixed submission:
"""
i - j = A[i] + A[j]
> i - A[i] = j + A[j]
i > j
"""
N = int(input())
high = list(map(int, input().split()))

ans = 0
calc = {}
for i in range(1, N+1):
  try:
    ans += calc[i - high[i-1]]
  except KeyError:
    pass
  if (i + high[i-1]) in calc.keys():
    calc[i + high[i-1]] += 1
  else:
    calc[i + high[i-1]] = 1

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
A, B, N = map(int, input().split())

ans = 0

for x in range(0, N+1):
  
  a = ( int((A*x)/B) - A*int(x/B) )
  if ans < a:
    ans = a
    
print(ans)

Fixed submission:
A, B, N = map(int, input().split())

#ans = ( int((A*x)/B) - A*int(x/B) )

if B <= N:
  x = B - 1
else:
  x = N
    
print(int((A*x)/B) - A*int(x/B))
Buggy python submission (verdict: Runtime Error):
S = input()

ans = 0

## 4桁
for i in range(0, len(S)-3):
  for j in range(i+3, len(S)):
    #print(S[i:j+1])
    if int(S[i:j+1]) % 2019 == 0:
      ans += 1

print(ans)

Fixed submission:
S, W = map(int, input().split())
 
if S <= W:
  print('unsafe')
else:
  print('safe')

Buggy python submission (verdict: Runtime Error):
S, W = map(int, intput().split())

if S <= W:
  print('unsafe')
else:
  print('safe')

Fixed submission:
S, W = map(int, input().split())
 
if S <= W:
  print('unsafe')
else:
  print('safe')
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())

gifts = []

for i in range(N):
  gift = input()
  if gift in gifts:
    pass
  else:
    gifts.append(gift)
    
print(len(gifts))

Fixed submission:
N = int(input())

gifts = []

for _ in range(N):
  gifts.append(input())
  
print(len(set(gifts)))
Buggy python submission (verdict: Time Limit Exceeded):
S = input()[::-1]
 
## 余りを0~2018で総数保持
counts = [0]*2019
## 0桁の余りは0
counts[0] = 1
 
num, d = 0, 1
 
for c in S:
  ## 右から~桁の数字
  num += int(c) * d
  num %= 2019
  
  ## 次の桁
  d *= 10
  #d %= 2019
  
  counts[num] += 1
  
ans = 0
for cnt in counts:
  ## nC2の計算
  ans += cnt * (cnt-1) //2
  
print(ans)

Fixed submission:
S = input()[::-1]
 
## 余りを0~2018で総数保持
counts = [0]*2019
## 0桁の余りは0
counts[0] = 1
 
num, d = 0, 1
 
for c in S:
  ## 右から~桁の数字
  num += int(c) * d
  num %= 2019
  
  ## 次の桁
  d *= 10
  d %= 2019
  
  counts[num] += 1
  
ans = 0
for cnt in counts:
  ## nC2の計算
  ans += cnt * (cnt-1) //2
  
print(ans)

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

## 余りを0~2018で総数保持
counts = [0]*2019
## 0桁の余りは0
counts[0] = 1

num, d = 0, 1

for c in s:
  ## 右から~桁の数字
  num += int(c) * d
  num %= 2019
  
  ## 次の桁
  d *= 10
  #d %= 2019
  
  counts[num] += 1
  
ans = 0
for cnt in counts:
  ## nC2の計算
  ans += cnt * (cnt-1) //2
  
print(ans)

Fixed submission:
S = input()[::-1]
 
## 余りを0~2018で総数保持
counts = [0]*2019
## 0桁の余りは0
counts[0] = 1
 
num, d = 0, 1
 
for c in S:
  ## 右から~桁の数字
  num += int(c) * d
  num %= 2019
  
  ## 次の桁
  d *= 10
  d %= 2019
  
  counts[num] += 1
  
ans = 0
for cnt in counts:
  ## nC2の計算
  ans += cnt * (cnt-1) //2
  
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
S = input()

ans = 0

## 4桁
for i in range(0, len(S)-3):
  for j in range(i+3, len(S)):
    if int(S[i:j+1]) % 2019 == 0:
      ans += 1

print(ans)

Fixed submission:
S = input()[::-1]
 
## 余りを0~2018で総数保持
counts = [0]*2019
## 0桁の余りは0
counts[0] = 1
 
num, d = 0, 1
 
for c in S:
  ## 右から~桁の数字
  num += int(c) * d
  num %= 2019
  
  ## 次の桁
  d *= 10
  d %= 2019
  
  counts[num] += 1
  
ans = 0
for cnt in counts:
  ## nC2の計算
  ans += cnt * (cnt-1) //2
  
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
 
ans = 0
mod = pow(10,9)+7
 
for k in range(K, N+2): ## K個以上で総数(N+1)
  ## 全個数の計算　## k個最大 ## k個最小
  ans += sum(range(N-k+1, N+1)) - sum(range(0, k)) + 1
  
print(ans % mod)

Fixed submission:
N, K = map(int, input().split())
 
ans = 0
mod = pow(10,9)+7
 
for k in range(K, N+2): ## K個以上で総数(N+1)
  ## 全個数の計算　## k個最大 ## k個最小
  ans += k*((N+1-k)+N)//2 - k*(0+k-1)//2 + 1
  
print(ans % mod)


## sum(range(N-k+1, N+1))
## k*((N+1-k)+N)/2

## sum(range(0, k))
## k*(0+k-1)/2

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

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

ans = 0

for k in range(K, N):
  ans += len(set(map(sum, itertools.combinations(range(N), k))))

print(ans%(10000000000+7)

Fixed submission:
N, K = map(int, input().split())
 
ans = 0
mod = pow(10,9)+7
 
for k in range(K, N+2): ## K個以上で総数(N+1)
  ## 全個数の計算　## k個最大 ## k個最小
  ans += k*((N+1-k)+N)//2 - k*(0+k-1)//2 + 1
  
print(ans % mod)


## sum(range(N-k+1, N+1))
## k*((N+1-k)+N)/2

## sum(range(0, k))
## k*(0+k-1)/2
Buggy python submission (verdict: Time Limit Exceeded):
k = int(input())

ans = 0
def gcd(x,y):
    while y:
        x, y = y, x % y
    return x

for i in range(1,k+1):
    for j in range(1,k+1):
        for s in range(1,k+1):
            ans += gcd(gcd(i,j),s)

print(ans)

Fixed submission:
from math import gcd
k=int(input())
ans=0
for i in range(1,k+1):
    for j in range(1,k+1):
        ans_=gcd(i,j)
        for l in range(1,k+1):
            ans+=gcd(ans_,l)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from itertools import product
from functools import reduce
# import math

def gcd(a, b):
  while b:
    a, b = b, a % b
  return a
  
def gcd_three(tup):
  return reduce(lambda a, b: gcd(a, b), tup)


K = int(input())
lst = range(1, K+1)
Sum = 0

for tup in product(lst, lst, lst):
  Sum += gcd_three(tup)
  
print(Sum)

Fixed submission:
from math import gcd
k=int(input())
ans=0
for i in range(1,k+1):
    for j in range(1,k+1):
        ans_=gcd(i,j)
        for l in range(1,k+1):
            ans+=gcd(ans_,l)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from itertools import product
from functools import reduce
import math
 
def gcd(tup):
  return reduce(lambda a, b: math.gcd(a, b), tup)


K = int(input())
lst = range(1, K+1)
memory = {}
Sum = 0


for tup in product(lst, lst, lst):
  if str(sorted(tup)) in memory.keys():
    Sum += memory[str(sorted(tup))]
  else:
    memory[str(sorted(tup))] =gcd(tup)
    Sum += memory[str(sorted(tup))]
  
print(Sum)

Fixed submission:
from math import gcd
k=int(input())
ans=0
for i in range(1,k+1):
    for j in range(1,k+1):
        ans_=gcd(i,j)
        for l in range(1,k+1):
            ans+=gcd(ans_,l)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from itertools import product
from functools import reduce
import math
 
def gcd(tup):
  return reduce(lambda a, b: math.gcd(a, b), tup)


K = int(input())
lst = range(1, K+1)
Sum = 0

for tup in product(lst, lst, lst):
  Sum += gcd(tup)
  
print(Sum)

Fixed submission:
from math import gcd
k=int(input())
ans=0
for i in range(1,k+1):
    for j in range(1,k+1):
        ans_=gcd(i,j)
        for l in range(1,k+1):
            ans+=gcd(ans_,l)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = input()

ans = 0

for i in range(0, N-2):
  for j in range(i+1, N-1):
    for k in range(j+1, N):
      
      if j-i == k-j:
        pass
      else:
        if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
          ans += 1
          
          
print(ans)

Fixed submission:
N = int(input())
S = input()

## 組み合わせの総数
ans = S.count('R') * S.count('B') * S.count('G')

## 除外
## j - i = k - j 
## k = 2*j -i

for i in range(0, N-2):
  for j in range(i+1, N-1):
    
    if 2*j-i >= N:
      break
    elif S[i] != S[j] and S[j] != S[2*j-i] and S[2*j-i] != S[i]:
      ans -= 1
  
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())

while(N > abs(N-K)):
  N = abs(N-K)
  
print(N)

Fixed submission:
N, K = map(int, input().split())
N = N % K

while(N > abs(N-K)):
  N = abs(N-K)
  
print(N)
Buggy python submission (verdict: Time Limit Exceeded):
K, N = [ int(i) for i in input().split()]

n = [int(i) for i in input().split()]
total = []

for i in range(0, N):
  distances = n
  if i > 0:
    distances[i-1] += K
    
  total.append(max(distances) - distances[i])
  
print(min(total))

Fixed submission:
K, N = map(int, input().split())
A = list(map(int, input().split()))
 
A.append(A[0]+K)
maxD = 0
 
for n in range(0, N):
  maxD = max(maxD, A[n+1] - A[n])
  
print(K - maxD)
Buggy python submission (verdict: Time Limit Exceeded):
n,m = map(int,input().split())
h = [int(x) for x in input().split()]
g = [[0 for j in range(n)] for i in range(n)]

for _ in range(m):
    a, b = map(int,input().split())
    g[a-1][b-1] = 1
    g[b-1][a-1] = 1

count = 0
for i in range(n):
    judge = True
    for j in range(n):
        if g[i][j] == 1:
            if h[i] <= h[j]:
                judge = False
                break
            else:
                judge = True
    if judge ==True:
        count+=1
print(count)


Fixed submission:
n,m = map(int,input().split())
h = [int(x) for x in input().split()]

result = [1]*n

for _ in range(m):
    a, b = map(int,input().split())
    if h[a-1] < h[b-1]:
        result[a-1] = 0
    elif h[a-1] > h[b-1]:
        result[b-1] = 0
    else:
        result[a-1] = 0
        result[b-1] = 0
print(result.count(1))