Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
def main():
  N, K = list(map(int, input().split()))
  A = list(map(int, input().split()))

  d = 60
  to = [[0] * N for _ in range(d)]

  for i in range(N):
    #テレポート距離が2^0のデータを入れる
    #これは入力A1〜ANと同じ
    to[0][i] = A[i] - 1 #0-indexedにする

  for i in range(1, d):
    for j in range(N):
      to[i][j] = to[i-1][to[i-1][j]]

  v = 0
  for i in range(d-1, -1, -1):
    l = 1 << i

    if(K >= l):
      v = to[i][v]
      K -= l

  print(v + 1)

if __name__ == "__main__":
  main()

Fixed submission:
from queue import Queue

def main():
    N, K = list(map(int, input().split()))
    A = list(map(int, input().split()))

    visited = [False] * N
    visited[0] = True
    p = [1]
    l = []
    r = []

    while(len(p) < N):
        v = p[-1] - 1
        n = A[v] - 1

        if(visited[n]):
            d = p.index(n+1)
            l = p[0:d]
            r = p[d:]
            break

        p.append(A[v])
        visited[n] = True

    if(len(l) == 0 and len(r) == 0):
        print(p[K%len(p)])
    else:
        if(K < len(p)):
            print(p[K])
        else:
            k = K - len(l)
            k %= len(r)
            print(r[k])
        

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
K = int(input())
total = 0
 
def gcd(a, b):
    if(a > b):
        a, b = b, a
 
    while(b > 0):
        r = a % b
        a = b
        b = r
 
    return a
 
 
for a in range(1, K+1):
    for b in range(1, K+1):
        res = gcd(a, b)
        for c in range(1, K+1):
           total += gcd(res, c)
 
 
print(total)

Fixed submission:
K = int(input())
total = 0

def gcd(a, b):
    if(a > b):
        a, b = b, a

    while(b > 0):
        r = a % b
        a = b
        b = r

    return a

dp = [[0 for i in range(K+1)] for j in range(K+1)]

for a in range(1, K+1):
    for b in range(1, K+1):
        if(dp[a][b] == 0):
            dp[a][b] = gcd(a, b)

        res = dp[a][b]

        for c in range(1, K+1):
            if(dp[res][c] == 0):
                dp[res][c] = gcd(res, c)

            total += dp[res][c]


print(total)

Buggy python submission (verdict: Time Limit Exceeded):
K = int(input())
total = 0

def gcd(a, b):
    if(a > b):
        a, b = b, a

    while(b > 0):
        r = a % b
        a = b
        b = r

    return a


for a in range(1, K+1):
    for b in range(1, K+1):
        res = gcd(a, b)
        for c in range(1, K+1):
           total += gcd(res, c)


print(total)

Fixed submission:
K = int(input())
total = 0

def gcd(a, b):
    if(a > b):
        a, b = b, a

    while(b > 0):
        r = a % b
        a = b
        b = r

    return a

dp = [[0 for i in range(K+1)] for j in range(K+1)]

for a in range(1, K+1):
    for b in range(1, K+1):
        if(dp[a][b] == 0):
            dp[a][b] = gcd(a, b)

        res = dp[a][b]

        for c in range(1, K+1):
            if(dp[res][c] == 0):
                dp[res][c] = gcd(res, c)

            total += dp[res][c]


print(total)

Buggy python submission (verdict: Time Limit Exceeded):
K = int(input())
total = 0

def gcd(a, b):
    if(a > b):
        a, b = b, a

    while(b > 0):
        r = a % b
        a = b
        b = r

    return a


for a in range(1, K+1):
    for b in range(1, K+1):
        for c in range(1, K+1):
           total += gcd(a, gcd(b, c))


print(total)

Fixed submission:
K = int(input())
total = 0

def gcd(a, b):
    if(a > b):
        a, b = b, a

    while(b > 0):
        r = a % b
        a = b
        b = r

    return a

dp = [[0 for i in range(K+1)] for j in range(K+1)]

for a in range(1, K+1):
    for b in range(1, K+1):
        if(dp[a][b] == 0):
            dp[a][b] = gcd(a, b)

        res = dp[a][b]

        for c in range(1, K+1):
            if(dp[res][c] == 0):
                dp[res][c] = gcd(res, c)

            total += dp[res][c]


print(total)
Buggy python submission (verdict: Time Limit Exceeded):
S = input()
Q = int(input())

res = S

is_rev = False

def add_char(s, f, c, is_rev):
  if(f == "1"):
    return c + s if not is_rev else s + c
  else:
    return s + c if not is_rev else c + s

for _ in range(Q):
  q = input().split()
  
  if(q[0] == '1'): # Ti = 1
    is_rev = not is_rev
  
  else: #Ti = 2
    res = add_char(res, q[1], q[2], is_rev)


print(res[::-1] if is_rev else res)

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

res = S

is_rev = False

before = []
after = []

def add_char(s, f, c, is_rev):
  if(f == "1"):
    before.append(c)
  else:
    after.append(c)

for _ in range(Q):
  q = input().split()
  
  if(q[0] == '1'): # Ti = 1
    is_rev = not is_rev
    before, after = after, before
  
  else: #Ti = 2
    add_char(res, q[1], q[2], is_rev)

before.reverse()

res = "".join(before) + (res[::-1] if is_rev else res) + "".join(after)

print(res)

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

res = S

def add_char(s, f, c):
  if(f == "1"):
    return c + s
  else:
    return s + c

for _ in range(Q):
  q = input().split()
  
  if(q[0] == '1'): # Ti = 1
    res = res[::-1]
  
  else: #Ti = 2
    res = add_char(res, q[1], q[2])


print(res)

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

res = S

is_rev = False

before = []
after = []

def add_char(s, f, c, is_rev):
  if(f == "1"):
    before.append(c)
  else:
    after.append(c)

for _ in range(Q):
  q = input().split()
  
  if(q[0] == '1'): # Ti = 1
    is_rev = not is_rev
    before, after = after, before
  
  else: #Ti = 2
    add_char(res, q[1], q[2], is_rev)

before.reverse()

res = "".join(before) + (res[::-1] if is_rev else res) + "".join(after)

print(res)
Buggy python submission (verdict: Runtime Error):

def dfs(node, paths, visited, n):
  # 全て訪問済みだったら全部を訪問できる経路として1を返す
  if not False in visited:
    return 1

  count = 0

  for nn in paths[node]:
    # 既に訪問済みなら処理をしない
    if(visited[nn]):
      continue

    visited[nn] = True
    count += dfs(nn, paths, visited, n)
    visited[nn] = False

  return count

def main():
  N, M = list(map(int, input().split()))
  paths = [[] for i in range(N)]
  visited = [False] * N

  for i in range(M):
    a, b = list(map(int, input().split()))
    paths[a-1].append(b-1)
    paths[b-1].append(a-1)

  visited[0] = True
  print(dfs(0, paths, visited, N))


if __name__ == "__main__":
    main()

Fixed submission:
import itertools

N = int(input())
P = tuple(map(int, input().split()))
Q = tuple(map(int, input().split()))

patterns = list(itertools.permutations(list(range(1,N+1))))

pi = 0
qi = 0

for index, pattern in enumerate(patterns):
  if P == pattern:
    pi = index
  if Q == pattern:
    qi = index

print(abs(pi - qi))
Buggy python submission (verdict: Time Limit Exceeded):

def main():
	S = list(input())
	n = len(S)
	ans = 0

	while(True):
		count = 0

		for i in range(0, n - 1):
			if(S[i] == 'B' and S[i+1] == 'W'):
				S[i], S[i+1] = S[i+1], S[i]
				count += 1

		if(count == 0):
			break

		ans += count
		
	print(ans)

if __name__ == "__main__":
	main()

Fixed submission:

def main():
	S = input()
	n = len(S)
	ans = 0

	black = 0
	f_pos = 0
	l_pos = 0

	for i, c in enumerate(S):
		if(c == 'B'):			
			f_pos += i
			black += 1

	l_pos = sum(list(range(n-1, n-1-black, -1)))
	

	ans = l_pos - f_pos

		
	print(ans)

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

def dfs(node, paths, visited, n):
  # 全て訪問済みだったら全部を訪問できる経路として1を返す
  if not False in visited:
    return 1

  count = 0

  for nn in paths[node]:
    # 既に訪問済みなら処理をしない
    if(visited[nn]):
      continue

    visited[nn] = True
    count += dfs(nn, paths, visited, n)
    visited[nn] = False

  return count

def main():
  N, M = list(map(int, input().split()))
  paths = [[] for i in range(M)]
  visited = [False] * M

  for i in range(M):
    a, b = list(map(int, input().split()))
    paths[a-1].append(b-1)
    paths[b-1].append(a-1)

  visited[0] = True
  print(dfs(0, paths, visited, N))


if __name__ == "__main__":
    main()

Fixed submission:

def dfs(node, paths, visited, n):
  # 全て訪問済みだったら全部を訪問できる経路として1を返す
  if not False in visited:
    return 1

  count = 0

  for nn in paths[node]:
    # 既に訪問済みなら処理をしない
    if(visited[nn]):
      continue

    visited[nn] = True
    count += dfs(nn, paths, visited, n)
    visited[nn] = False

  return count

def main():
  N, M = list(map(int, input().split()))
  paths = [[] for i in range(N)]
  visited = [False] * N

  for i in range(M):
    a, b = list(map(int, input().split()))
    paths[a-1].append(b-1)
    paths[b-1].append(a-1)

  visited[0] = True
  print(dfs(0, paths, visited, N))


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
n=int(input())
l=[]
r=[]
for i in range(n):
    a,b=map(int,input().split())
    r.append(a)
    l.append(b)
m=max(l)
s=sum(r)
if s<m:
    print("Yes")
else:
    print("No")

Fixed submission:
s=str(input())
c=0
for i in range(len(s)-1):
    if s[i]==s[i+1]:
        c+=1
if c:
    print("Bad")
else:
    print("Good")
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())

L = [0] * (n + 1)
for x in range(1, n + 1):
    for y in range(1, n - x):
        for z in range(1, n - x - y):
            tmp = x * x + y * y + z * z + x * y + y * z + z * x
            if tmp > n:
                continue
            L[tmp] += 1

for l in L[1:]:
    print(l)


Fixed submission:
import math

n = int(input())
max = int(math.sqrt(n) + 1)
L = [0] * (n + 1)
for x in range(1, max):
    for y in range(1, max):
        for z in range(1, max):
            tmp = x * x + y * y + z * z + x * y + y * z + z * x
            if tmp > n:
                continue
            L[tmp] += 1

for i in range(1, n + 1):
    print(L[i])

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

L = [0] * (n + 1)
for x in range(1, n + 1):
    for y in range(1, n - x):
        for z in range(1, n - x - y):
            tmp = x * x + y * y + z * z + x * y + y * z + z * x
            if tmp > n:
                continue
            L[tmp] += 1

for l in L[1:]:
    print(l)

Fixed submission:
import math

n = int(input())
max = int(math.sqrt(n) + 1)
L = [0] * (n + 1)
for x in range(1, max):
    for y in range(1, max):
        for z in range(1, max):
            tmp = x * x + y * y + z * z + x * y + y * z + z * x
            if tmp > n:
                continue
            L[tmp] += 1

for i in range(1, n + 1):
    print(L[i])

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

L = [0] * (n + 1)
for x in range(1, n + 1):
    for y in range(1, n - x):
        for z in range(1, n - x - y):
            tmp = x * x + y * y + z * z + x * y + y * z + z * x
            if tmp <= n:
                L[tmp] += 1
            # print(x, y , z)

for l in L[1:]:
    print(l)

Fixed submission:
import math

n = int(input())
max = int(math.sqrt(n) + 1)
L = [0] * (n + 1)
for x in range(1, max):
    for y in range(1, max):
        for z in range(1, max):
            tmp = x * x + y * y + z * z + x * y + y * z + z * x
            if tmp > n:
                continue
            L[tmp] += 1

for i in range(1, n + 1):
    print(L[i])
Buggy python submission (verdict: Runtime Error):
x, n = map(int, input().split())
if n > 0:
    P = list(map(int, input().split()))
    Q = sorted(
        [[i, abs(i - x)] for i in range(1, 101) if i not in P],
        key=lambda x:x[0])
    Q.sort(key=lambda x:x[1])
    print(Q[0][0])
else:
    print(x)


Fixed submission:
x, n = map(int, input().split())
if n > 0:
    P = list(map(int, input().split()))
else:
    P = []

ans, dist = 0, 1000
for i in range(-200, 200):
    if i not in P:
        if abs(i - x) < dist:
            dist = abs(i - x)
            ans = i
print(ans)

Buggy python submission (verdict: Runtime Error):
x, n = map(int, input().split())
if n > 0:
    P = list(map(int, input().split()))
    Q = sorted(
        [[i, abs(i - x)] for i in range(1, 101) if i not in P],
        key=lambda x:x[1])
    print(Q[0][0])
else:
    print(x)

Fixed submission:
x, n = map(int, input().split())
if n > 0:
    P = list(map(int, input().split()))
else:
    P = []

ans, dist = 0, 1000
for i in range(-200, 200):
    if i not in P:
        if abs(i - x) < dist:
            dist = abs(i - x)
            ans = i
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import math
def get_prime(n):
    if n <= 1:
        return []
    prime = [2]
    if n > 2:
        limit = int(math.sqrt(n))
        odd = [i for i in range(3, n + 1, 2)]
        while limit >= odd[0]:
            prime.append(odd[0])
            odd = [j for j in odd if j % odd[0] != 0]
        prime += odd
    return prime

from collections import defaultdict
def prime_factorization(n):
    if n <= 1:
        return False
    else:
        # print(int(math.sqrt(n)))
        prime = get_prime(int(math.sqrt(n)))
        dct = defaultdict(int)
        for p in prime:
            while n % p == 0:
                dct[p] += 1
                n //= p
        if n != 1:
            dct[n] += 1
        dct = dict(dct)
        return dct


n = int(input())
select = []
for i in range(2, n):
    pf = prime_factorization(i)
    if len(pf) == 1:
        p, e = list(pf.keys())[0], list(pf.values())[0]
        z = p ** e
        if n % z == 0 and z not in select:
            select.append(z)
            n //= z
    if n == 1:
        break

print(len(select))

Fixed submission:
import math
def get_prime(n):
    if n <= 1:
        return []
    prime = [2]
    if n > 2:
        limit = int(math.sqrt(n))
        odd = [i for i in range(3, n + 1, 2)]
        while limit >= odd[0]:
            prime.append(odd[0])
            odd = [j for j in odd if j % odd[0] != 0]
        prime += odd
    return prime

from collections import defaultdict
def prime_factorization(n):
    if n <= 1:
        return {}
    else:
        # print(int(math.sqrt(n)))
        prime = get_prime(int(math.sqrt(n)))
        dct = defaultdict(int)
        for p in prime:
            while n % p == 0:
                dct[p] += 1
                n //= p
        if n != 1:
            dct[n] += 1
        dct = dict(dct)
        return dct

n = int(input())
pf = prime_factorization(n)

Z = []
for k, v in pf.items():
    for i in range(1, v + 1):
        Z.append(k ** i)
Z.sort()
count = 0
for z in Z:
    if n % z == 0:
        count += 1
        n //= z
    if n == 1:
        break

print(count)
Buggy python submission (verdict: Runtime Error):
T = input()
n = T.count("?")

S = T.replace("?", "D")
count1 = S.count("D") + S.count("PD")

for i, v in enumerate(T):
    if v == "?":
        if i == 0:
            if T[i + 1] == "D":
                T = T.replace("?", "P", 1)
            else:
                T = T.replace("?", "D", 1)
        else:
            if T[i - 1] == "P":
                T = T.replace("?", "D", 1)
            else:
                T = T.replace("?", "P", 1)

count2 = T.count("D") + T.count("PD")

print(T if count1 < count2 else S)

Fixed submission:
T = input()
print(T.replace("?", "D"))

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

n = T.count("?")

ans = ""
count = 0
for i in range(2 ** n):
    S = T
    for j in range(n):
        if ((i >> j) & 1):
            S = S.replace("?", "P", 1)
        else:
            S = S.replace("?", "D", 1)
    tmp = S.count("D") + S.count("PD")
    count = max(count, tmp)
    if count == tmp:
        ans = S

print(ans)

Fixed submission:
T = input()
print(T.replace("?", "D"))

Buggy python submission (verdict: Time Limit Exceeded):
T = input()
n = T.count("?")

ans = ""
count = 0
for i in range(2 ** n):
    S = T
    for j in range(n):
        if ((i >> j) & 1):
            S = S.replace("?", "P", 1)
        else:
            S = S.replace("?", "D", 1)
    tmp = S.count("D") + S.count("PD")
    count = max(count, tmp)
    if count == tmp:
        ans = S

print(ans)

Fixed submission:
T = input()
print(T.replace("?", "D"))
Buggy python submission (verdict: Time Limit Exceeded):
x = int(input())

for a in range(0, 10 ** 9):
    for b in range(0, 10 ** 9):
        ans = a ** 5 - (-b) ** 5
        if ans == x:
            print(a, -b)
            exit()

Fixed submission:
x = int(input())
for a in range(120):
    for b in range(-120, 120):
        if a ** 5 - b ** 5 == x:
            print(a, b)
            exit()
Buggy python submission (verdict: Time Limit Exceeded):
a, b, n = map(int, input().split())

max = 0
for i in range(1, n + 1):
    tmp = ((a * i) // b) - (a * (i // b))
    max = tmp if tmp > max else max

print(max)

Fixed submission:
a, b, n = map(int, input().split())
x = min(n, b - 1)
print(((a * x) // b) - (a * (x // b)))
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
boss = list(map(str, input().split()))

for i in range(1, n + 1):
    count = 0
    for b in boss:
        if b == str(i):
            count += 1
    print(count)

Fixed submission:
n = int(input())
boss = list(map(str, input().split()))
ans = [0] * n
for b in boss:
    ans[int(b) - 1] += 1
for a in ans:
    print(a)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
boss = list(map(str, input().split()))
exective = set(boss)

for i in range(1, n + 1):
    if str(i) in exective:
        print(boss[i - 1 :].count(str(i)))
    else:
        print(0)

Fixed submission:
n = int(input())
boss = list(map(str, input().split()))
ans = [0] * n
for b in boss:
    ans[int(b) - 1] += 1
for a in ans:
    print(a)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
boss = list(map(str, input().split()))
exective = sorted(set(boss))

for i in range(1, n + 1):
    if str(i) in exective:
        print(boss.count(str(i)))
    else:
        print(0)

Fixed submission:
n = int(input())
boss = list(map(str, input().split()))
ans = [0] * n
for b in boss:
    ans[int(b) - 1] += 1
for a in ans:
    print(a)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
boss = list(map(str, input().split()))

for i in range(1, n + 1):
    print(boss.count(str(i)))

Fixed submission:
n = int(input())
boss = list(map(str, input().split()))
ans = [0] * n
for b in boss:
    ans[int(b) - 1] += 1
for a in ans:
    print(a)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
boss = list(map(str, input().split()))
for i in range(1, n + 1):
    print(boss.count(str(i)))

Fixed submission:
n = int(input())
boss = list(map(str, input().split()))
ans = [0] * n
for b in boss:
    ans[int(b) - 1] += 1
for a in ans:
    print(a)
Buggy python submission (verdict: Time Limit Exceeded):
import math
from functools import reduce
num = int(input())
ans = 0
for i in range(1, num + 1):
    for j in range(1, num + 1):
        for k in range(1, num + 1):
            ans += math.gcd(math.gcd(i, j), k)
print(ans)

Fixed submission:
import math
num = int(input())
ans = 0
for i in range(1, num + 1):
    for j in range(1, num + 1):
        tmp = math.gcd(i, j)
        for k in range(1, num + 1):
            ans += math.gcd(tmp, k)

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import math
from functools import reduce
def gcd(*nums):
    return reduce(math.gcd, nums)

num = int(input())
ans = 0
for i in range(1, num + 1):
    for j in range(1, num + 1):
        for k in range(1, num + 1):
            ans += gcd(i, j, k)

print(ans)

Fixed submission:
import math
num = int(input())
ans = 0
for i in range(1, num + 1):
    for j in range(1, num + 1):
        tmp = math.gcd(i, j)
        for k in range(1, num + 1):
            ans += math.gcd(tmp, k)

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

r = len([i for i in range(n) if s[i] == "R"])
g = len([i for i in range(n) if s[i] == "G"])
b = len([i for i in range(n) if s[i] == "B"])

count = 0
for i in range(n):
    for j in range(i + 1, n):
        k = 2 * j - i
        if k >= n:
            break
        if all([s[i] != s[j], s[j] != s[k], s[k] != s[i]]):
            count += 1

print(r * g * b - count)

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

r = len([i for i in range(n) if s[i] == "R"])
g = len([i for i in range(n) if s[i] == "G"])
b = len([i for i in range(n) if s[i] == "B"])

count = 0
for i in range(n):
    for j in range(i + 1, n):
        k = 2 * j - i
        if k >= n:
            break
        if s[i] != s[j] and s[j] != s[k] and s[k] != s[i]:
            count += 1

print(r * g * b - count)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
s = input()
R = [i for i in range(n) if s[i] == "R"]
G = [i for i in range(n) if s[i] == "G"]
B = [i for i in range(n) if s[i] == "B"]
count = 0
for r in R:
    for g in G:
        for b in B:
            pos = sorted([r, g, b])
            if pos[1] - pos[0] != pos[2] - pos[1]:
                count += 1
print(count)

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

r = len([i for i in range(n) if s[i] == "R"])
g = len([i for i in range(n) if s[i] == "G"])
b = len([i for i in range(n) if s[i] == "B"])

count = 0
for i in range(n):
    for j in range(i + 1, n):
        k = 2 * j - i
        if k >= n:
            break
        if s[i] != s[j] and s[j] != s[k] and s[k] != s[i]:
            count += 1

print(r * g * b - count)
Buggy python submission (verdict: Time Limit Exceeded):
k, n = map(int, input().split())
a = list(map(int, input().split()))

a.append(k + a[0])
each_dist = [(a[i] - a[i - 1]) for i in range(1, n + 1)]
ans = k
for i in range(n):
    all_dist = sum(each_dist[: i] + each_dist[i + 1: ])
    if all_dist < ans:
        ans = all_dist

print(ans)

Fixed submission:
k, n = map(int, input().split())
a = list(map(int, input().split()))
a.append(k + a[0])

each_dist = [(a[i] - a[i - 1]) for i in range(1, n + 1)]
print(k - max(each_dist))