Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-

import sys
import os

N, M = list(map(int, input().split()))
students = []
checkpoints = []

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

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

for student in students:
    min_dist = float('inf')
    min_i = None
    for i, checkpoint in enumerate(checkpoints):
        manhattan_dist = abs(checkpoint[0] - student[0]) + abs(checkpoint[1] - student[1])
        if manhattan_dist < min_dist:
            min_dist = manhattan_dist
            min_i = i
    print(min_i + 1)


Fixed submission:
# -*- coding: utf-8 -*-

import sys
import os


N, M = list(map(int, input().split()))
students = []
checkpoints = []

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

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

for student in students:
    min_dist = float('inf')
    min_i = None
    for i, checkpoint in enumerate(checkpoints):
        manhattan_dist = abs(checkpoint[0] - student[0]) + abs(checkpoint[1] - student[1])
        if manhattan_dist < min_dist:
            min_dist = manhattan_dist
            min_i = i
    print(min_i + 1)

Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-

import sys
import os
import pprint
from queue import Queue


N, M = list(map(int, input().split()))
students = []
checkpoints = []

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

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

for student in students:
    min_dist = float('inf')
    min_i = None
    for i, checkpoint in enumerate(checkpoints):
        manhattan_dist = abs(checkpoint[0] - student[0]) + abs(checkpoint[1] - student[1])
        if manhattan_dist < min_dist:
            min_dist = manhattan_dist
            min_i = i
    print(min_i + 1)


Fixed submission:
# -*- coding: utf-8 -*-

import sys
import os


N, M = list(map(int, input().split()))
students = []
checkpoints = []

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

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

for student in students:
    min_dist = float('inf')
    min_i = None
    for i, checkpoint in enumerate(checkpoints):
        manhattan_dist = abs(checkpoint[0] - student[0]) + abs(checkpoint[1] - student[1])
        if manhattan_dist < min_dist:
            min_dist = manhattan_dist
            min_i = i
    print(min_i + 1)
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
a_list = [int(input()) for _ in range(n)]

dp = [1] * n

for i in range(n):
    for j in range(max(0, i - 1000), i):
        if abs(a_list[i] - a_list[j]) <= k:
            dp[i] = max(dp[i], dp[j] + 1)

ans = max(dp)
print(ans)

Fixed submission:
n, k = map(int, input().split())
a_list = [int(input()) for _ in range(n)]

dp = [1] * n

for i in range(n):
    for j in range(max(0, i - 100), i):
        if abs(a_list[i] - a_list[j]) <= k:
            dp[i] = max(dp[i], dp[j] + 1)

ans = max(dp)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
a_list = [int(input()) for _ in range(n)]


dp = [1] * n

for i in range(n):
    for j in range(0, i):
        if abs(a_list[i] - a_list[j]) <= k:
            dp[i] = max(dp[i], dp[j] + 1)

ans = max(dp)
print(ans)

Fixed submission:
n, k = map(int, input().split())
a_list = [int(input()) for _ in range(n)]

dp = [1] * n

for i in range(n):
    for j in range(max(0, i - 100), i):
        if abs(a_list[i] - a_list[j]) <= k:
            dp[i] = max(dp[i], dp[j] + 1)

ans = max(dp)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
mod = 998244353

s_list = []
for _ in range(k):
    l, r = map(int, input().split())
    s_list += list(range(l, r + 1))
S = set(sorted(s_list))

ans_array = [0] * (n + 1)
ans_array[1] = 1
for i in range(1, n):
    for d in S:
        if d + i > n:
            break
        ans_array[d + i] = (ans_array[d + i] + ans_array[i]) % mod


print(ans_array[n])

Fixed submission:
# 累積和を用いたdpの高速か

n, k = map(int, input().split())
mod = 998244353

lr_list = [list(map(int, input().split())) for _ in range(k)]

dp = [0] * (n + 1)
dp[1] = 1
sdp = [0] * (n + 1)
sdp[1] = 1
for i in range(2, n + 1):
    for j in range(k):
        right = max(0, i - lr_list[j][0])
        left = max(0, i - lr_list[j][1] - 1)
        dp[i] = (dp[i] + sdp[right] - sdp[left]) % mod
    sdp[i] = sdp[i - 1] + dp[i]

print(dp[n])
Buggy python submission (verdict: Runtime Error):
import numpy as np

s = input()
t = input()

len_s = len(s)
len_t = len(t)

ma = 0
for i in range(len_s - len_t + 1):
    ma = max(ma, np.sum(np.array(list(s[i: i + len_t])) == np.array(list(t))))

ans = len_t - ma

print(ans)

Fixed submission:
import numpy as np

s = input()
t = input()

len_s = len(s)
len_t = len(t)

ma = 0
for i in range(len_s - len_t + 1):
    ma = max(ma, np.sum(np.array(list(s[i: i + len_t])) == np.array(list(t))))

ans = len_t - ma

print(ans)
Buggy python submission (verdict: Runtime Error):
class union_find:
    def __init__(self, node_num):
        self.root_array = [-1] * node_num

    def root(self, x):
        if self.root_array[x] < 0:
            return x
        else:
            return self.root_array[x]

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        if self.root_array[x] > self.root_array[y]:
            x, y = y, x
        self.root_array[x] += self.root_array[y]
        self.root_array[y] = x

    def size(self, x):
        return -self.root_array[self.root(x)]


def solve(n, m, ab_array):
    uf = union_find(n)
    for ab in ab_array:
        a, b = ab
        uf.unite(a - 1, b - 1)

    ans = 0
    for i in range(n):
        ans = max(ans, uf.size(i))

    return ans

if __name__ == '__main__':
    n, m = map(int, input().split())
    ab_array = [list(map(int, input().split())) for _ in range(m)]
    ans = solve(n, m, ab_array)
    print(ans)

Fixed submission:
from collections import deque

n, m = map(int, input().split())
ab_array = [list(map(int, input().split())) for _ in range(m)]

ad_sum_array = [0] * n
ad_array = [set() for _ in range(n)]

for ab in ab_array:
    a, b = ab
    ad_array[a - 1].add(b - 1)
    ad_array[b - 1].add(a - 1)

check_array = [False] * n

def bfs(node_num):
    queue = deque([node_num])
    check_array[node_num] = True
    num = 1

    while queue:
        node = queue.popleft()
        for ad in ad_array[node]:
            if not check_array[ad]:
                check_array[ad] = True
                queue.append(ad)
                num += 1
    return num

ans = 0
for i in range(n):
    if not check_array[i]:
        ans = max(ans, bfs(i))

print(ans)
Buggy python submission (verdict: Runtime Error):
n, k = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))

max_score = -float('inf')

for i in range(n):
    loop_score_array = []
    loop_score = 0
    loop_len = 0
    pos = i
    while True:
        pos = p[pos] - 1
        loop_score += c[pos]
        loop_score_array.append(loop_score)
        loop_len+=1
        if pos == i:
            break
    for i, score in enumerate(loop_score_array):
        if k-i-1 < 0:
            continue
        loop_num = (k-i-1)//loop_len
        score_sum = score + max(0, loop_score)*loop_num
        max_score = max(score_sum, max_score)
print(max_score)

Fixed submission:
S = input()

day = 0
max_day = 0
for s in S:
    if s == 'R':
        day += 1
        max_day = max(day, max_day)
    else:
        day = 0

print(max_day)
Buggy python submission (verdict: Runtime Error):
N = int(input())


for i in range(1, N+1):
    sum = 0

    range_x = int((i-5)**0.5)+1 if i-5 >0 else 0
    s = set()
    for x in range(1, range_x):
        flag = False
        if x in s:
            continue
        range_y = int((i-x**2-x-3)**0.5)+1 if i-x**2-2*x-2 > 0 else 0
        for y in range(x, range_y):
            if y in s:
                continue
            range_z = int((i-x**2-y**2-x*y-x-y)**0.5)+1 if i-x**2-y**2-x*y-x-y > 0 else 0
            for z in range(y, range_z):
                if z in s:
                    continue
                if x**2 + y**2 + z**2 + x*y + y*z + z*x == i:
                    num = len(set([x,y,z]))
                    sum += 6 if num == 3 else 3 if num==2 else 1
                    s = s | set([x,y,z])
                    flag = True
                    break
            if flag:
                break

    print(sum)

Fixed submission:
L, R, d = list(map(int, input().split()))

num = 0
for i in range(L, R+1):
    if i%d == 0:
        num += 1

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

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

conf_max = 0
for p in itertools.permutations(A):
    conf = 0
    for i in range(1, N):
        conf += min(p[i-1], p[0])
    if conf_max < conf:
        conf_max = conf

print(conf_max)

Fixed submission:
N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)

conf_max = 0
for i in range(1, N):
    conf_max += A[i//2]

print(conf_max)
Buggy python submission (verdict: Runtime Error):
N, M, K = list(map(int, input().split()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))

A_sum = [0]
B_sum = [0]
for i in range(N):
    A_sum.append(A_sum[i]+A[i])
for i in range(M):
    B_sum.append(B_sum[i]+B[i])


num = 0
J = M
for i in range(N+1):
    if A_sum[i] > K:
        break
    for j in (J,-1,-1):
        if A_sum[i] + B_sum[j] <= K:
            if num < i+j:
                num = i+j
            J = j
            break

print(num)


Fixed submission:
a = int(input())
print(a+a**2+a**3)
Buggy python submission (verdict: Time Limit Exceeded):
N, M, K = list(map(int, input().split()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))

A_sum = [0]
B_sum = [0]
for i in range(N):
    A_sum.append(A_sum[i]+A[i])
for i in range(M):
    B_sum.append(B_sum[i]+B[i])


num = 0
for i in range(N+1):
    for j in range(M+1):
        if A_sum[i]+B_sum[j] <= K:
            if num < i+j:
                num = i+j

print(num)


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

A_sum = [0]
B_sum = [0]
for i in range(N):
    A_sum.append(A_sum[i]+A[i])
for i in range(M):
    B_sum.append(B_sum[i]+B[i])

num = 0
J = M
for i in range(N+1):
    if A_sum[i] > K:
        break
    for j in reversed(range(J+1)):
        if A_sum[i] + B_sum[j] <= K:
            if num < i+j:
                num = i+j
            J = j
            break

print(num)
Buggy python submission (verdict: Runtime Error):
import numpy as np

N = int(input())
A = np.array(list(map(int, input().split())))
Q = int(input())
bc = [list(map(int, input().split())) for _ in range(Q)]

for i in range(Q):
    A[A==bc[i][0]] = bc[i][1]
    print(sum(A))

Fixed submission:
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
bc = [list(map(int, input().split())) for _ in range(Q)]

mem = [0]*(10**5)

sum = 0
for i in A:
    mem[i-1] += 1
    sum += i

for q in range(Q):
    b = bc[q][0]
    if mem[b-1] != 0:
        c = bc[q][1]
        num = mem[b-1]
        mem[c-1] += num
        mem[b-1] = 0
        sum = sum - num*b + num*c
    print(sum)

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np

N = int(input())
A = np.array(list(map(int, input().split())))
Q = int(input())
bc = [list(map(int, input().split())) for _ in range(Q)]

for i in range(Q):
    A[A==bc[i][0]] = bc[i][1]
    print(sum(A))

Fixed submission:
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
bc = [list(map(int, input().split())) for _ in range(Q)]

mem = [0]*(10**5)

sum = 0
for i in A:
    mem[i-1] += 1
    sum += i

for q in range(Q):
    b = bc[q][0]
    if mem[b-1] != 0:
        c = bc[q][1]
        num = mem[b-1]
        mem[c-1] += num
        mem[b-1] = 0
        sum = sum - num*b + num*c
    print(sum)
Buggy python submission (verdict: Runtime Error):
from collections import Counter
N = int(input())
A = sorted(list(map(int, input().split())))
count = Counter(A)

data = [True]*N
A = list(set(A))

for i in range(N):
    if data[i]:
        for j in range(i+1,N):
            # print(i,j)
            if A[j]%A[i]==0:
                data[j]=False

ans = len([i for i in range(N) if data[i] and count[A[i]]==1])
print(ans)


Fixed submission:
from collections import Counter
N = int(input())
A = sorted(list(map(int, input().split())))
count = Counter(A)

max_len_A = 10**6+1
data = [0]*max_len_A
A = list(set(A))

for a in A:
    if data[a]==0:
        for j in range(a+a, max_len_A, a):
            data[j]+=1


ans = len([a for a in A if data[a]==0 and count[a]==1])
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))

mod = 10**18
ans = 1
for i in range(N):
    ans *= A[i]

if ans > mod:
    print(-1)
    exit()

print(ans)

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

mod = 10**18
ans = 1
for i in range(N):
    ans *= A[i]
    if ans > mod:
        if 0 in A:
            print(0)
        else:
            print(-1)
        exit()

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

root = [A[0]]

if k<= n:
    for i in range(k-1):
        root.append(A[root[-1]-1])
    print(root[-1])
    exit()
else:
    for i in range(n-1):
        next = A[root[-1]-1]
        if not next in root:
            root.append(next)
        else:
            index = root.index(next)
            f = root[:index]
            loop = root[index:]
    len_f = len(f)
    len_loop = len(loop)
    print(loop[(k-len_f)%len_loop-1])

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

now = A[0]
root_set = set([now])
root_array = [now]
if k<= n:
    for i in range(k-1):
        now = A[now-1]
        root_set.add(now)
        root_array.append(now)
    print(root_array[-1])
else:
    for i in range(n-1):
        now = A[now-1]
        if not now in root_set:
            root_set.add(now)
            root_array.append(now)
        else:
            index = root_array.index(now)
            f = root_array[:index]
            loop = root_array[index:]
            break
    len_f = len(f)
    len_loop = len(loop)
    print(loop[(k-len_f)%len_loop-1])
Buggy python submission (verdict: Time Limit Exceeded):
import math

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

under = int(b/a + 1)
top = min(n, b)
ans = 0
for i in range(under, top+1):
    ans = max(math.floor(a*i/b)-a*math.floor(i/b), ans)

print(ans)

Fixed submission:
import math

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

top = min(n, b-1)
ans = math.floor(a*top/b)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
s = input()
len_s = len(s)
s_array = [int(i) for i in s]

mod = 2019
mod_array = [0]*mod

num = 0
mod_array[0] += 1
for i in range(len_s):
    num = (num + (10 ** i) * s_array[len_s - i - 1])
    mod_array[num%mod] += 1

ans = 0
for i in mod_array:
    ans += (i * (i - 1)) / 2

print(int(ans))

Fixed submission:
s = input()
len_s = len(s)
s_array = [int(i) for i in s]

mod = 2019
mod_array = [0]*mod

num = 0
mod_array[0] += 1
for i in range(len_s):
    num = pow(10, i, mod) * s_array[len_s - i - 1] + num
    num %= mod
    mod_array[num] += 1

ans = 0
for i in mod_array:
    ans += (i * (i - 1)) / 2

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

def operation(x, k):
    return abs(x - k)

while True:
    nn = operation(n, k)
    if nn >= n:
        ans = n
        break
    else:
        n = nn

print(ans)

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

d = n // k
ans = min(abs(n - k * d), abs(n - k * (d + 1)))

print(ans)
Buggy python submission (verdict: Runtime Error):
import numpy as np

k, n = map(int, input().split())
a_array = list(map(int, input().split()))

a_array.append(k + a_array[0])

a_diff = np.diff(a_array)
ans = np.sum(a_diff) - np.max(a_diff)
print(ans)

Fixed submission:
import numpy as np

k, n = map(int, input().split())
a_array = list(map(int, input().split()))

a_array.append(k + a_array[0])

a_diff = np.diff(a_array)
ans = np.sum(a_diff) - np.max(a_diff)
print(ans)
Buggy python submission (verdict: Runtime Error):
S = input()
Q = int(input())

lS = ''
for _ in range(Q):
    query = input().split()
    if query[0] == '1':
        lS, S = S, lS
    else:
        if query[1] == '1':
            lS += query[2]
        else:
            S += query[2]

print(lS[::-1] + S)

Fixed submission:
s = input()

s_count_A = s.count('A')

if s_count_A == 0 or s_count_A == 3:
    ans = 'No'
else:
    ans = 'Yes'

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

flag = True
lS = ''
for _ in range(Q):
    query = input().split()
    if query[0] == '1':
        lS, S = S, lS
    else:
        if query[1] == '1':
            lS += query[2]
        else:
            S += query[2]

print(lS[::-1] + S)

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

lS = ''
for _ in range(Q):
    query = input().split()
    if query[0] == '1':
        lS, S = S, lS
    else:
        if query[1] == '1':
            lS += query[2]
        else:
            S += query[2]

print(lS[::-1] + S)

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

flag = True
lS = ''
for _ in range(Q):
    query = input()
    if query[0] == '1':
        lS, S = S, lS
    else:
        _, f, c = query.split()
        if f == '1':
            lS += c
        else:
            S += c

print(lS[::-1] + S)

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

lS = ''
for _ in range(Q):
    query = input().split()
    if query[0] == '1':
        lS, S = S, lS
    else:
        if query[1] == '1':
            lS += query[2]
        else:
            S += query[2]

print(lS[::-1] + S)

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

flag = True
for _ in range(Q):
    query = input()
    if query[0] == '1':
        flag = not flag
    else:
        _, f, c = query.split()
        if (f == '1' and flag) or (f == '2' and not flag):
            S = c + S
        else:
            S = S + c
if not flag:
    S = S[::-1]

print(S)

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

lS = ''
for _ in range(Q):
    query = input().split()
    if query[0] == '1':
        lS, S = S, lS
    else:
        if query[1] == '1':
            lS += query[2]
        else:
            S += query[2]

print(lS[::-1] + S)

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

flag = True
for _ in range(Q):
    query = input()
    if query[0] == '1':
        flag = not flag
    else:
        _, f, c = query.split()
        if (f == '1' and flag) or (f == '2' and not flag):
            S = c + S
        else:
            S = S + c
if not flag:
    S = S[::-1]

print(S)

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

lS = ''
for _ in range(Q):
    query = input().split()
    if query[0] == '1':
        lS, S = S, lS
    else:
        if query[1] == '1':
            lS += query[2]
        else:
            S += query[2]

print(lS[::-1] + S)

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


for _ in range(Q):
    query = input()
    if query[0] == '1':
        S = S[::-1]
    else:
        _, f, c = query.split()
        if f == '1':
            S = c + S
        else:
            S = S + c

print(S)

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

lS = ''
for _ in range(Q):
    query = input().split()
    if query[0] == '1':
        lS, S = S, lS
    else:
        if query[1] == '1':
            lS += query[2]
        else:
            S += query[2]

print(lS[::-1] + S)
Buggy python submission (verdict: Time Limit Exceeded):
class Unionfind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def root (self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.root(self.parents[x])
            return self.parents[x]

    def connect(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def isConnect(self, x):
        return self.root(x) == self.root(y)

    def size(self, x):
        return -self.parents[self.root(x)]

N, K = map(int, input().split())
P = list(map(lambda x: int(x) - 1, input().split()))
C = list(map(int, input().split()))

INF = 10 ** 18
ans = -INF
dp = [[-INF] * (N + 1) for _ in range(N)]
uf = Unionfind(N)

for i in range(N):
    dp[i][0] = 0
    now = i
    for j in range(min(N, K)):
        now = P[now]
        dp[i][j + 1] = dp[i][j] + C[now]
        uf.connect(i, now)
        ans = max(ans, dp[i][j + 1])

for i in range(N):
    M = uf.size(i)
    if dp[i][M] <= 0:
        continue
    roop = K // M
    move = K % M
    if move == 0:
        roop -= 1
        move = M
    for j in range(move):
        ans = max(ans, dp[i][M] * roop + dp[i][j + 1])

print(ans)


Fixed submission:
class Unionfind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def root (self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.root(self.parents[x])
            return self.parents[x]

    def connect(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def isConnect(self, x):
        return self.root(x) == self.root(y)

    def size(self, x):
        return -self.parents[self.root(x)]

N, K = map(int, input().split())
P = list(map(lambda x: int(x) - 1, input().split()))
C = list(map(int, input().split()))

INF = 10 ** 18
ans = -INF
dp = [[-INF] * (N + 1) for _ in range(N)]
uf = Unionfind(N)

for i in range(N):
    dp[i][0] = 0
    now = i
    for j in range(min(N, K)):
        now = P[now]
        dp[i][j + 1] = dp[i][j] + C[now]
        uf.connect(i, now)
        ans = max(ans, dp[i][j + 1])

for i in range(N):
    M = uf.size(i)
    if dp[i][M] <= 0:
        continue
    roop = K // M
    move = K % M
    if move == 0:
        roop -= 1
        move = M
    for j in range(move):
        ans = max(ans, dp[i][M] * roop + dp[i][j + 1])

print(ans)