Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
s = input()[::-1]
mod = 13
p = 10 ** 9 + 7
dic = defaultdict(int)
dic[0] = 1

for i in range(len(s)):
    tmp = defaultdict(int)
    if s[i] == "?":
        for j in range(10):
            d = j * 10 ** i % mod
            for k, v in dic.items():
                tmp[(k + d) % mod] += v
                tmp[(k + d) % mod] %= p
    else:
        d = int(s[i]) * 10 ** i % mod
        for k, v in dic.items():
            tmp[(k + d) % mod] = v
            tmp[(k + d) % mod] %= p
    dic = tmp
print(dic[5] % p)


Fixed submission:
from collections import defaultdict
s = input()[::-1]
mod = 13
p = 10 ** 9 + 7
dic = defaultdict(int)
dic[0] = 1

for i in range(len(s)):
    tmp = defaultdict(int)
    if s[i] == "?":
        for j in range(10):
            d = j * pow(10, i, mod)
            for k, v in dic.items():
                tmp[(k + d) % mod] += v
                tmp[(k + d) % mod] %= p
    else:
        d = int(s[i]) * pow(10, i, mod)
        for k, v in dic.items():
            tmp[(k + d) % mod] = v
    dic = tmp
print(dic[5] % p)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
s = input()[::-1]
mod = 13
p = 10 ** 9 + 7
dic = defaultdict(int)
dic[0] = 1

for i in range(len(s)):
    tmp = defaultdict(int)
    if s[i] == "?":
        for j in range(10):
            d = j * 10 ** i % mod
            for k, v in dic.items():
                tmp[(k + d) % mod] += v
                tmp[(k + d) % mod] %= p
    else:
        d = int(s[i]) * 10 ** i % mod
        for k, v in dic.items():
            tmp[(k + d) % mod] = v
            tmp[(k + d) % mod] %= p
    dic = tmp
print(dic[5] % p)


Fixed submission:
from collections import defaultdict
s = input()[::-1]
mod = 13
p = 10 ** 9 + 7
dic = defaultdict(int)
dic[0] = 1

for i in range(len(s)):
    tmp = defaultdict(int)
    if s[i] == "?":
        for j in range(10):
            d = j * pow(10, i, mod)
            for k, v in dic.items():
                tmp[(k + d) % mod] += v
                tmp[(k + d) % mod] %= p
    else:
        d = int(s[i]) * pow(10, i, mod)
        for k, v in dic.items():
            tmp[(k + d) % mod] = v
    dic = tmp
print(dic[5] % p)
Buggy python submission (verdict: Time Limit Exceeded):
def solve():
    import sys
    n, *s = map(int, sys.stdin.read().split())
    for i in range(n):
        t = s[:i] + s[i + 1:]
        print(max(t))


solve()


Fixed submission:
def solve():
    from bisect import bisect_left
    import sys
    n, *s = map(int, sys.stdin.read().split())
    t = sorted(s)
    for ss in s:
        x = bisect_left(t, ss)
        if x == n - 1:
            print(t[-2])
        else:
            print(t[-1])



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

res = set()
for i in range(n - 1):
    for j in range (i + 1, n):
        res.add(s[i] ^ s[j])

ref = set(s)
print("Yes" if all(c in res for c in ref) else "No")


Fixed submission:
from collections import Counter
n = int(input())
s = Counter(list(map(int, input().split())))

if s[0] == n:
    print("Yes")
elif len(s) == 2 and s[0] == n // 3:
    print("Yes")
elif len(s) == 3:
    res = 0
    num = set()
    for k, v in s.items():
        res ^= k
        num.add(v)
    if not res and len(num) == 1:
        print("Yes")
    else:
        print("No")
else:
    print("No")
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
lis = list(map(int, input().split()))
a = n // 2
res = sum(lis)


def dams(i, a, lis):
    su = 0
    for j in range(a):
        b = (i + (2 * j + 1)) % len(lis)
        su += lis[b]
    return su


ans = []
for i in range(n):
    ans.append(res - 2 * dams(i, a, lis))
print(*ans)


Fixed submission:
import sys
input = sys.stdin.readline

n = int(input())
lis = list(map(int, input().split()))
res = sum(lis)
su = [0] * n

for i in range(n):
    if i < 2:
        su[i] = lis[i]
    else:
        su[i] = su[i-2] + lis[i]

ans = []
ans_a = ans.append

for i in range(n):
    if i == 0:
        b = su[-2]
        ans_a(res-2*b)
    elif i == 1:
        b = su[-1] - su[i-1]
        ans_a(res-2*b)
    elif i == n:
        b = su[-1] - lis[-1]
        ans_a(res-2*b)
    elif i % 2 == 0:
        b = su[-2] - su[i-1] + su[i-2]
        ans_a(res-2*b)
    else:
        b = su[-1] - su[i-1] + su[i-2]
        ans_a(res-2*b)
print(*ans)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
lis = list(map(int, input().split()))
a = n // 2
res = sum(lis)


def dams(i, a, lis):
    su = 0
    for j in range(a):
        b = (i + (2 * j + 1)) % len(lis)
        su += lis[b]
    return su


ans = []
for i in range(n):
    ans.append(res - 2 * dams(i, a, lis))
print(*ans)


Fixed submission:
import sys
input = sys.stdin.readline

n = int(input())
lis = list(map(int, input().split()))
res = sum(lis)
su = [0] * n

for i in range(n):
    if i < 2:
        su[i] = lis[i]
    else:
        su[i] = su[i-2] + lis[i]

ans = []
ans_a = ans.append

for i in range(n):
    if i == 0:
        b = su[-2]
        ans_a(res-2*b)
    elif i == 1:
        b = su[-1] - su[i-1]
        ans_a(res-2*b)
    elif i == n:
        b = su[-1] - lis[-1]
        ans_a(res-2*b)
    elif i % 2 == 0:
        b = su[-2] - su[i-1] + su[i-2]
        ans_a(res-2*b)
    else:
        b = su[-1] - su[i-1] + su[i-2]
        ans_a(res-2*b)
print(*ans)
Buggy python submission (verdict: Time Limit Exceeded):
def solve():
    import sys
    n, m, *LR = map(int, sys.stdin.read().split())
    L = LR[::2]
    R = LR[1::2]
    res = set(range(1, n + 1))
    for l, r in zip(L, R):
        x = set(range(l, r + 1))
        res &= x
    print(len(res))


solve()


Fixed submission:
def solve():
    import sys
    n, m, *LR = map(int, sys.stdin.read().split())
    L = LR[::2]
    R = LR[1::2]
    l = max(L)
    r = min(R)
    print(max(0, r - l + 1))


solve()
Buggy python submission (verdict: Time Limit Exceeded):
import heapq
n, m = map(int, input().split())
a = [-1*int(x) for x in input().split()]
heapq.heapify(a)

for i in range(m):
    x, y = map(int, input().split())
    for j in range(x):
        heapq.heappush(a, -y)

res = 0
for i in range(n):
    res += heapq.heappop(a)*-1
print(res)


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

for i in range(m):
    x, y = map(int, input().split())
    a.append((x, y))

a.sort(key=lambda x:x[1], reverse=True)
res = 0

for j, k in a:
    while j > 0 and n > 0:
        res += k
        j -= 1
        n -= 1
print(res)

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

for i in range(m):
    x, y = map(int, input().split())
    for j in range(x):
        a.append(y)

a.sort(reverse=True)
print(sum(a[:n]))


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

for i in range(m):
    x, y = map(int, input().split())
    a.append((x, y))

a.sort(key=lambda x:x[1], reverse=True)
res = 0

for j, k in a:
    while j > 0 and n > 0:
        res += k
        j -= 1
        n -= 1
print(res)
Buggy python submission (verdict: Runtime Error):
from collections import deque

h, w = map(int, input().split())
inf = 10 ** 6
a = [[0] * (w + 2), *[[0] + [inf] * w + [0] for _ in range(h)], [0] * (w + 2)]
d = deque()

for i in range(h):
    for j, k in enumerate(input()):
        if k == "#":
            a[i + 1][j + 1] = 0
            d.append((i + 1, j + 1))

stp = ((0, 1), (0, -1), (1, 0), (-1, 0))
res = 0

while d:
    x, y = d.popleft()
    for k, l in stp:
        nx, ny = x + k, y + l
        if a[x][y] + 1 < a[nx][ny]:
            a[nx][ny] = a[x][y] + 1
            res = max(res, a[nx][ny])
            d.append((nx, ny))
print(res)


Fixed submission:
from collections import deque

h, w = map(int, input().split())
inf = 10 ** 6
a = [[0] * (w + 2)] + [[0] + [inf] * w + [0] for _ in range(h)] + [[0] * (w + 2)]
d = deque()

for i in range(h):
    for j, k in enumerate(input()):
        if k == "#":
            a[i + 1][j + 1] = 0
            d.append((i + 1, j + 1))

stp = ((0, 1), (0, -1), (1, 0), (-1, 0))
res = 0

while d:
    x, y = d.popleft()
    for k, l in stp:
        nx, ny = x + k, y + l
        if a[x][y] + 1 < a[nx][ny]:
            a[nx][ny] = a[x][y] + 1
            res = max(res, a[nx][ny])
            d.append((nx, ny))
print(res)
Buggy python submission (verdict: Runtime Error):
from math import gcd


def main():
    #####segfunc######
    def segfunc(x, y):
        return gcd(x, y)

    def init(init_val):
        # set_val
        for i in range(n):
            seg[i + num - 1] = init_val[i]
            # built
        for i in range(num - 2, -1, -1):
            seg[i] = segfunc(seg[2 * i + 1], seg[2 * i + 2])

    def update(k, x):
        k += num - 1
        seg[k] = x
        while k:
            k = (k - 1) // 2
            seg[k] = segfunc(seg[k * 2 + 1], seg[k * 2 + 2])

    def query(p, q):
        if q <= p:
            return ide_ele
        p += num - 1
        q += num - 2
        res = ide_ele
        while q - p > 1:
            if p & 1 == 0:
                res = segfunc(res, seg[p])
            if q & 1 == 1:
                res = segfunc(res, seg[q])
                q -= 1
            p = p // 2
            q = (q - 1) // 2
        if p == q:
            res = segfunc(res, seg[p])
        else:
            res = segfunc(segfunc(res, seg[p]), seg[q])
        return res

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

    #####単位元######
    ide_ele = 0

    # num:n以上の最小の2のべき乗
    num = 2 ** (n - 1).bit_length()
    seg = [ide_ele] * 2 * num
    init(a)

    ans = -1
    for i in range(n):
        ans = max(ans, gcd(query(0, i), query(i + 1, n)))
    print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
from fractions import gcd


def main():
    #####segfunc######
    def segfunc(x, y):
        return gcd(x, y)

    def init(init_val):
        # set_val
        for i in range(n):
            seg[i + num - 1] = init_val[i]
            # built
        for i in range(num - 2, -1, -1):
            seg[i] = segfunc(seg[2 * i + 1], seg[2 * i + 2])

    def update(k, x):
        k += num - 1
        seg[k] = x
        while k:
            k = (k - 1) // 2
            seg[k] = segfunc(seg[k * 2 + 1], seg[k * 2 + 2])

    def query(p, q):
        if q <= p:
            return ide_ele
        p += num - 1
        q += num - 2
        res = ide_ele
        while q - p > 1:
            if p & 1 == 0:
                res = segfunc(res, seg[p])
            if q & 1 == 1:
                res = segfunc(res, seg[q])
                q -= 1
            p = p // 2
            q = (q - 1) // 2
        if p == q:
            res = segfunc(res, seg[p])
        else:
            res = segfunc(segfunc(res, seg[p]), seg[q])
        return res

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

    #####単位元######
    ide_ele = 0

    # num:n以上の最小の2のべき乗
    num = 2 ** (n - 1).bit_length()
    seg = [ide_ele] * 2 * num
    init(a)

    ans = -1
    for i in range(n):
        ans = max(ans, gcd(query(0, i), query(i + 1, n)))
    print(ans)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
n, k = map(int, input().split())
s = input()
res = []

if s[0] == "0":
    res.append(0)

res.append(1)

for i in range(1, n):
    if s[i] == s[i - 1]:
        res[-1] += 1
    else:
        res.append(1)

if s[-1] == "0":
    res.append(0)

l = len(res)
su = [0] * (l + 1)
for i in range(l):
    su[i + 1] = su[i] + res[i]

mil = min(l, 2 * k + 1)

ans = 1
for i in range(0, l - mil + 1, 2):
    ans = max(ans, su[2 * k + 1 + i] - su[i])
print(ans)


Fixed submission:
n, k = map(int, input().split())
s = input()
res = []

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

l = len(res)
su = [0] * (l + 1)
for i in range(l):
    su[i + 1] = su[i] + res[i]

mil = min(l, 2 * k + 1)

ans = 1
for i in range(0, l - mil + 1, 2):
    ans = max(ans, su[mil + i] - su[i])
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
s = list(map(int, input().split()))
inf = 10 ** 8
dp = [inf] * n
dp[0] = 0

for j in range(1, n):
    buf = [dp[i] + abs(s[j]-s[i]) for i in range(max(0, j - k), j)]
    dp[j] = min(buf)
print(dp[-1])


Fixed submission:
def main():
    n, k = map(int, input().split())
    s = list(map(int, input().split()))
    inf = 10 ** 8
    dp = [inf] * n
    dp[0] = 0

    for j in range(1, n):
        buf = [dp[i] + abs(s[j]-s[i]) for i in range(max(0, j - k), j)]
        dp[j] = min(buf)
    print(dp[-1])

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

def solve():
    n = int(input())
    val = []
    for i in range(min(n, 3)):
        x, y, h = map(int, input().split())
        val.append([x+y+h, -x+y+h, x-y+h, -x-y+h])
    base = [[1, 1, 1], [1, -1, 1], [1, 1, -1], [1, -1, -1]]
    ans = []
    for i, xx in enumerate(base):
        for j, yy in enumerate(base):
            for k, zz in enumerate(base):
                A = np.array([xx, yy, zz])
                Y = np.array([[val[0][i]], [val[1][j]], [val[2][k]]])
                try:
                    AA = np.linalg.inv(A)
                except np.linalg.LinAlgError as e:
                    if 'Singular matrix' in str(e):
                        continue
                    else:
                        raise
                ans.append(np.dot(AA, Y).tolist())
    print(int(*ans[5][1]), int(*ans[5][2]), int(*ans[5][0]))

solve()


Fixed submission:
def solve():
    n = int(input())
    X, Y, H = [], [], []
    for i in range(n):
        x, y, h = map(int, input().split())
        X.append(x), Y.append(y), H.append(h)

    for cx in range(101):
        for cy in range(101):
            res = []
            for x, y, h in zip(X, Y, H):
                if h == 0:
                    continue
                hh = h + abs(x - cx) + abs(y - cy)
                res.append(hh)
            if len(set(res)) == 1:
                flg = True
                for x, y, h in zip(X, Y, H):
                    if h != max(res[0] - abs(x - cx) - abs(y - cy), 0):
                        flg = False
                if flg:
                    print(cx, cy, res[0])

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

def solve():
    n, m = map(int, input().split())
    d = m // n
    p = m % n
    res = max(1, gcd(d, d + p))
    while d > 1:
        d -= 1
        q = m - n * d
        res = max(res, gcd(d, d + q))
    print(res)


solve()

Fixed submission:
from math import gcd

def solve():
    n, m = map(int, input().split())
    d = m // n
    p = m % n
    res = max(1, gcd(d, d + p))
    if p == 0:
        print(res)
        exit()
    while d > res:
        d -= 1
        p += n
        if p % d == 0:
            res = max(res, d)
    print(res)


solve()

Buggy python submission (verdict: Runtime Error):
def solve():
    n, m = map(int, input().split())
    d = m // n
    p = m % n
    res = max(1, gcd(d, d + p))
    while d > 1:
        d -= 1
        q = m - n * d
        res = max(res, gcd(d, d + q))
    print(res)


solve()

Fixed submission:
from math import gcd

def solve():
    n, m = map(int, input().split())
    d = m // n
    p = m % n
    res = max(1, gcd(d, d + p))
    if p == 0:
        print(res)
        exit()
    while d > res:
        d -= 1
        p += n
        if p % d == 0:
            res = max(res, d)
    print(res)


solve()
Buggy python submission (verdict: Runtime Error):
# ref https://atcoder.jp/contests/agc025/submissions/7307839
import numpy as np
from card3.void.stop_watch import stop_watch

@stop_watch
def main():
    n = int(input())
    L, R = [], []
    for i in range(n):
        l, r = map(int, input().split())
        L.append(l)
        R.append(r)
    ll = np.array(L); ll.sort(); ll = ll[::-1]
    rr = np.array(R); rr.sort()

    lll = ll.cumsum()
    rrr = rr.cumsum()

    x = (lll - rrr).max()
    y = (lll[1:] - rrr[:-1]).max()
    z = (lll[:-1] - rrr[1:]).max()

    print(2 * max(x, y, z))
if __name__ == '__main__':
    main()

Fixed submission:
# ref https://atcoder.jp/contests/agc025/submissions/7307839
import numpy as np

def main():
    n = int(input())
    L, R = [], []
    for i in range(n):
        l, r = map(int, input().split())
        L.append(l)
        R.append(r)
    ll = np.array(L); ll.sort(); ll = ll[::-1]
    rr = np.array(R); rr.sort()

    lll = ll.cumsum()
    rrr = rr.cumsum()

    x = (lll - rrr).max()
    y = (lll[1:] - rrr[:-1]).max()
    z = (lll[:-1] - rrr[1:]).max()

    print(2 * max(x, y, z))
if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))

cnt, su, r = 0, 0, 0
for l in range(n):
    su = 0
    r = l
    while r < n and su + a[r] == su ^ a[r]:
        su += a[r]
        r += 1
        cnt += 1
    if l == 0 and r == n:
        print(n * (n + 1) // 2)
        exit()
print(cnt)


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

cnt, su, r = 0, 0, 0
for l in range(n):
    while r < n and su + a[r] == su ^ a[r]:
        su += a[r]
        r += 1
    cnt += r - l
    if l == r:
        r += 1
    else:
        su -= a[l]
print(cnt)

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

cnt = 0
for i in range(n):
    s = 0
    x = 0
    for j in range(i, n):
        s += A[j]
        x ^= A[j]
        if s == x:
            cnt += 1
        else:
            break
print(cnt)


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

cnt, su, r = 0, 0, 0
for l in range(n):
    while r < n and su + a[r] == su ^ a[r]:
        su += a[r]
        r += 1
    cnt += r - l
    if l == r:
        r += 1
    else:
        su -= a[l]
print(cnt)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
n, m = map(int, input().split())
s = list(map(int, input().split()))
g = [[] for i in range(n)]

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

q = deque()
chk = [0] * n
res = []

for i in range(n):
    tmp = set()
    if not chk[i]:
        q.append(i)
        while q:
            v = q.pop()
            chk[v] = 1
            tmp.add(v)
            for u in g[v]:
                if chk[u] == 1:
                    continue
                q.append(u)
        res.append(tmp)

ans = 0
for re in res:
    tmp2 = set()
    for r in re:
        tmp2.add(s[r] - 1)
    ans += len(tmp2 & re)
print(ans)


Fixed submission:
from collections import deque
n, m = map(int, input().split())
s = list(map(int, input().split()))
g = [[] for i in range(n)]

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

q = deque()
chk = [0] * n
res = []

for i in range(n):
    tmp = set()
    if not chk[i]:
        q.append(i)
        while q:
            v = q.pop()
            chk[v] = 1
            tmp.add(v)
            for u in g[v]:
                if chk[u] == 1:
                    continue
                q.append(u)
        res.append(tmp)

ans = 0
for re in res:
    tmp2 = set()
    for r in re:
        tmp2.add(s[r] - 1)
    ans += len(tmp2 & re)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import combinations
from collections import deque
s = input()
n = int(input())

le = len(s)
seed = tuple(combinations(range(le + 1), 2))

res = deque()
res.append("zzzzzzzzzzzzzzzzzzzzzzz")
res.append("zzzzzzzzzzzzzzzzzzzzzzz")
res.append("zzzzzzzzzzzzzzzzzzzzzzz")
res.append("zzzzzzzzzzzzzzzzzzzzzzz")
res.append("zzzzzzzzzzzzzzzzzzzzzzz")

for i, j in seed:
    ch = s[i:j]
    if ch in res:
        continue
    elif ch < max(res):
        res.remove(max(res))
        res.append(ch)

ans = sorted(res)
print(ans[n - 1])


Fixed submission:
from itertools import combinations
s = input()
n = int(input())

le = len(s)
tmp = s[:5]

for i in range(le - 4):
    tmp = min(tmp, s[i:i+5])

seed = tuple(combinations(range(min(6, le+1)), 2))
res = set()
for i, j in seed:
    res.add(tmp[i:j])
ans = sorted(res)
print(ans[n - 1])

Buggy python submission (verdict: Time Limit Exceeded):
from itertools import combinations
s = input()
n = int(input())

le = len(s)
seed = tuple(combinations(range(le + 1), 2))

res = set()
for i, j in seed:
    res.add(s[i:j])

ans = sorted(res)
print(ans[n - 1])


Fixed submission:
from itertools import combinations
s = input()
n = int(input())

le = len(s)
tmp = s[:5]

for i in range(le - 4):
    tmp = min(tmp, s[i:i+5])

seed = tuple(combinations(range(min(6, le+1)), 2))
res = set()
for i, j in seed:
    res.add(tmp[i:j])
ans = sorted(res)
print(ans[n - 1])
Buggy python submission (verdict: Runtime Error):
def main():
    n = int(input())
    for _ in range(n):
        a, b = map(int, input().split())
        ref = a * b - 1
        rng = int(ref ** 0.5)
        res = rng * 2
        if ref // rng == rng:
            res -= 2
        elif a > rng and b > rng:
            res -= 0
        else:
            res -= 1
        print(res)
if __name__ == '__main__':
    main()

Fixed submission:
def main():
    n = int(input())
    for _ in range(n):
        a, b = map(int, input().split())
        ref = a * b - 1
        rng = int(ref ** 0.5) - 2
        while rng ** 2 < a * b:
            rng += 1
        rng -= 1
        if a == b or abs(a - b) == 1:
            print(2 * min(a, b) - 2)
        elif rng * (rng + 1) >= a * b:
            print(2 * rng - 2)
        else:
            print(2 * rng - 1)
if __name__ == '__main__':
    main()