Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
a = input()
b = input()
c = input()

def match(c1, c2):
    return c1 == c2 or c1 == "?" or c2 == "?"

def check(x, y, xy):
    for i in range(len(x)):
        for j in range(len(y)):
            if not match(x[i], y[j]):
                xy[i - j + 50000] = True


l_a = len(a)
l_b = len(b)
l_c = len(c)

ab = [False] * 100000
ac = [False] * 100000
bc = [False] * 100000

check(a, b, ab)
check(a, c, ac)
check(b, c, bc)

l_max = 2000
ans = 3 * l_max
for i in range(-2 * l_max, 2 * l_max + 1):
    for j in range(-2 * l_max, 2 * l_max + 1):
        if not ab[i+50000] and not ac[j+50000] and not bc[j-i+50000]:
            lb = min(0, min(i, j))
            ub = max(l_a, max(l_b + i, l_c + j))
            ans = min(ans, ub - lb)
            
print(ans)



Fixed submission:
a = input()
b = input()
c = input()

def match(c1, c2):
    return c1 == c2 or c1 == "?" or c2 == "?"

def check(x, y, l_m=2000):
    xy = [0] * (l_m * 8 + 1)
    mid = l_m * 4
    for i in range(len(x)):
        for j in range(len(y)):
            if not match(x[i], y[j]):
                xy[i - j + mid] = 1
    return xy

l_a = len(a)
l_b = len(b)
l_c = len(c)

ab = check(a, b)
ac = check(a, c)
bc = check(b, c)

l_m = 2000
mid = l_m * 4

ans = 3 * l_m
for i in range(-2 * l_m, 2 * l_m + 1):
    if ab[i + mid]:
        continue
    for j in range(-2 * l_m, 2 * l_m + 1):
        if ac[j + mid] or bc[j - i + mid]:
            continue

        lb = min(0, min(i, j))
        ub = max(l_a, max(l_b + i, l_c + j))
        ans = min(ans, ub - lb)

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
S = input()
Q = int(input())
X = [input() for _ in range(Q)]

ans = S
r = 0  # r=0: order, r=1: reverse
for i in range(Q):
    q, *x = X[i].split()
    if q == "1":
        r = abs(r - 1)
    else:
        f, c = x
        if (r == 0 and f == "1") or (r == 1 and f == "2"):
            ans = c + ans
        else:
            ans += c
            
print(ans if r == 0 else ans[::-1])


Fixed submission:
from collections import deque

S = input()
Q = int(input())
X = [input() for _ in range(Q)]

ans = deque(S)
r = 0  # r=0: order, r=1: reverse
for i in range(Q):
    q, *x = X[i].split()
    if q == "1":
        r = abs(r - 1)
    else:
        f, c = x
        if (r == 0 and f == "1") or (r == 1 and f == "2"):
            ans.appendleft(c)
        else:
            ans.append(c)
            
print("".join(ans) if r == 0 else "".join(ans)[::-1])
Buggy python submission (verdict: Runtime Error):
N, K, *A = map(int, open(0).read().split())

neg = sorted([-a for a in A if a < 0])
pos = sorted([a for a in A if a >= 0])

def _count_pair_neg(x):
    x = -x
    res = 0

    MAX = len(neg)
    i = 0
    for n in reversed(neg):
        while i < MAX and n * pos[i] < x:
            i += 1
            
        res += len(pos) - i
    return res


def _count_pair_pos(x):
    res = 0

    # Negative list
    i = 0
    MAX = len(neg)
    for n in reversed(neg):
        if n * n <= x:
            res -= 1
            
        while i < MAX and neg[i] * n <= x:
            i += 1
        res += i
        
    # Positive list
    i = 0
    MAX = len(pos)
    for n in reversed(pos):
        if n * n <= x:
            res -= 1
            
        while i < MAX and pos[i] * n <= x:
            i += 1
        res += i
        
    # Devide by 2 for counting the same pair twice
    res //= 2
    res += len(neg) * len(pos)
    return res


def count_pair(x):
    if x < 0:
        return _count_pair_neg(x)
    
    return _count_pair_pos(x)


# Bounds
lb = 0
ub = 2 * 10 ** 18 + 2

while ub - lb > 1:
    mid = (ub + lb) // 2
    if count_pair(mid - 10 ** 18 - 1) < K:
        lb = mid
    else:
        ub = mid

print(ub - 10 ** 18 - 1)


Fixed submission:
N, K, *A = map(int, open(0).read().split())

neg = sorted([-a for a in A if a < 0])
pos = sorted([a for a in A if a >= 0])

def _count_pair_neg(x):
    x = -x
    res = 0

    MAX = len(pos)
    i = 0
    for n in reversed(neg):
        while i < MAX and n * pos[i] < x:
            i += 1
            
        res += MAX - i
    return res


def _count_pair_pos(x):
    res = 0

    # Negative list
    i = 0
    MAX = len(neg)
    for n in reversed(neg):
        if n * n <= x:
            res -= 1
            
        while i < MAX and neg[i] * n <= x:
            i += 1
        res += i
        
    # Positive list
    i = 0
    MAX = len(pos)
    for n in reversed(pos):
        if n * n <= x:
            res -= 1
            
        while i < MAX and pos[i] * n <= x:
            i += 1
        res += i
        
    # Devide by 2 for counting the same pair twice
    res //= 2
    res += len(neg) * len(pos)
    return res


def count_pair(x):
    if x < 0:
        return _count_pair_neg(x)
    
    return _count_pair_pos(x)


# Bounds
lb = 0
ub = 2 * 10 ** 18 + 2

while ub - lb > 1:
    mid = (ub + lb) // 2
    if count_pair(mid - 10 ** 18 - 1) < K:
        lb = mid
    else:
        ub = mid

print(ub - 10 ** 18 - 1)
Buggy python submission (verdict: Runtime Error):

r1, c1, r2, c2 = map(int, input().split())

MAX = 10 ** 6 + 1
MOD = 10 ** 9 + 7

# Factorial
fac = [0] * (MAX + 1)
fac[0] = 1
fac[1] = 1

# Inverse
inv = [0] * (MAX + 1)
inv[1] = 1

# Inverse factorial
finv = [0] * (MAX + 1)
finv[0] = 1
finv[1] = 1

for i in range(2, MAX + 1):
    fac[i] = fac[i - 1] * i % MOD
    inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
    finv[i] = finv[i - 1] * inv[i] % MOD


def f(r, c):
    return fac[r + c] * finv[r] * finv[c] % MOD


ans = 0
for i in range(c1, c2 + 1):
    ans += f(r2, i + 1) - f(r1 - 1, i + 1)
    ans %= MOD
print(ans)


Fixed submission:
r1, c1, r2, c2 = map(int, input().split())

MAX = 2 * 10 ** 6 + 2
MOD = 10 ** 9 + 7

# Factorial
fac = [0] * (MAX + 1)
fac[0] = 1
fac[1] = 1
for i in range(2, MAX + 1):
    fac[i] = fac[i - 1] * i % MOD
    
# Inverse factorial
finv = [0] * (MAX + 1)
finv[MAX] = pow(fac[MAX], MOD - 2, MOD)
for i in reversed(range(1, MAX + 1)):
    finv[i - 1] = finv[i] * i % MOD

def f(r, c):
    return fac[r + c] * finv[r] * finv[c]

ans = 0
for i in range(c1, c2 + 1):
    ans += f(r2, i + 1) - f(r1 - 1, i + 1)
    ans %= MOD
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict


def prime_factor(n):
    d = defaultdict(int)
    for i in range(2, n + 1):
        if i * i > n:
            break

        while n % i == 0:
            d[i] += 1
            n //= i

    if n != 1:
        d[n] += 1

    return d


N = int(input())
X = list(map(int, input().split()))
MOD = 10 ** 9 + 7

ctr = defaultdict(int)
buf = []
for n in X:
    d = prime_factor(n)
    buf.append(d)
    for key in d:
        ctr[key] = max(ctr[key], d[key])

ans = 0
for i, n in enumerate(X):
    cur = 1
    for key in ctr:
        cnt = ctr[key] - buf[i][key]
        if cnt > 0:
            cur = cur * pow(key, cnt, MOD) % MOD

    ans += cur
    ans %= MOD

print(ans)


Fixed submission:
from fractions import gcd
from functools import reduce

N, *A = map(int, open(0).read().split())

def lcm(x, y):
    return x * y // gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

MOD = 10 ** 9 + 7
num = lcm_list(A)
print(sum(num * pow(v, MOD - 2, MOD) for v in A) % MOD)

Buggy python submission (verdict: Time Limit Exceeded):
from fractions import gcd
from functools import reduce

N, *A = map(int, open(0).read().split())

def lcm(x, y):
    return x * y // gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

MOD = 10 ** 9 + 7
num = lcm_list(A)
print(sum(num // v for v in A) % MOD)


Fixed submission:
from fractions import gcd
from functools import reduce

N, *A = map(int, open(0).read().split())

def lcm(x, y):
    return x * y // gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

MOD = 10 ** 9 + 7
num = lcm_list(A)
print(sum(num * pow(v, MOD - 2, MOD) for v in A) % MOD)
Buggy python submission (verdict: Runtime Error):
from functools import reduce
from math import gcd

N, M, *A = map(int, open(0).read().split())

def lcm(x, y):
    return x * y // gcd(x, y)

n = reduce(lcm, [v // 2 for v in A])
print(-(-(M // n) // 2))


Fixed submission:
from fractions import gcd
from functools import reduce

def lcm(x, y):
    return x * y // gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

def sub_by_2(n):
    cnt = 0
    while n % 2 == 0:
        cnt += 1
        n //= 2
    return cnt

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

lcm_2 = [sub_by_2(v // 2) for v in A]
if all(lcm_2[0] == v for v in lcm_2):
    num = lcm_list([v // 2 for v in A])
    ans = M // num
    print(ans // 2 + ans % 2)
else:
    print(0)
Buggy python submission (verdict: Time Limit Exceeded):

N = int(input())
S = input()

dp = [[[False] * 1000 for _ in range(4)] for _ in range(N + 1)]
dp[0][0][0] = True
for i in range(N):
    for j in range(4):
        for k in range(1000):
            if not dp[i][j][k]:
                continue

            dp[i + 1][j][k] = dp[i][j][k]
            to = k * 10 + int(S[i])
            if j < 3 and to < 1000:
                dp[i + 1][j + 1][to] = dp[i][j][k]

print(sum(dp[-1][-1]))


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

ctr = [0] * 1000
ans = 0
for i in range(1000):
    v1 = i // 100
    v2 = i // 10 - v1 * 10
    v3 = i - v1 * 100 - v2 * 10
    
    p1 = S.find(str(v1))
    if p1 < 0:
        continue
        
    p2 = S[p1+1:].find(str(v2))
    if p2 < 0:
        continue
        
    p3 = S[p1+p2+2:].find(str(v3))
    ans += int(p3 >= 0)
    
print(ans)

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

dp = [[[False] * 1000 for _ in range(4)] for _ in range(N + 1)]
dp[0][0][0] = True

for i in range(N):
    for j in range(4):
        for k in range(1000):
            if not dp[i][j][k]:
                continue
                
            # Not choose S[i]
            dp[i + 1][j][k] = True
            
            # Choose S[i]
            if j < 3:
                dp[i + 1][j + 1][k * 10 + int(S[i])] = True
            
print(sum(dp[-1][-1]))


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

ctr = [0] * 1000
ans = 0
for i in range(1000):
    v1 = i // 100
    v2 = i // 10 - v1 * 10
    v3 = i - v1 * 100 - v2 * 10
    
    p1 = S.find(str(v1))
    if p1 < 0:
        continue
        
    p2 = S[p1+1:].find(str(v2))
    if p2 < 0:
        continue
        
    p3 = S[p1+p2+2:].find(str(v3))
    ans += int(p3 >= 0)
    
print(ans)
Buggy python submission (verdict: Runtime Error):
import math

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

if a ** 2 * b * 0.5 < x:
    d = a ** 3 / (2 * (a ** 2 * b - x))
else:
    d = 2 * x / (a * b ** 2)
print(90 - math.atan(d) * 180 / math.pi)


Fixed submission:
from math import atan, pi
a, b, x = map(int, input().split())

if x > (a ** 2 * b / 2):
    print(atan(2 * (a ** 2 * b - x) / a ** 3) * 180 / pi)
else:
    print(atan((a * b ** 2) / (2 * x)) * 180 / pi)

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

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

if a ** 2 * b * 0.5 < x:
    d = a ** 3 / (2 * (a ** 2 * b - x))
else:
    d = 2 * x / (a * b ** 2)
print(90 - math.degrees(math.atan(d)))


Fixed submission:
from math import atan, pi
a, b, x = map(int, input().split())

if x > (a ** 2 * b / 2):
    print(atan(2 * (a ** 2 * b - x) / a ** 3) * 180 / pi)
else:
    print(atan((a * b ** 2) / (2 * x)) * 180 / pi)
Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappop, heappush
N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))

A.sort()
F.sort(reverse=True)

pq = []
for i in range(N):
    heappush(pq, (-A[i] * F[i], F[i]))
    
for _ in range(K):
    c, u = heappop(pq)
    heappush(pq, (c + u, u))
    
print(max(0, -min(v for v, _ in pq)))




Fixed submission:
from heapq import heappop, heappush
N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))

def ok(x):
    cnt = 0
    for i in range(N):
        current = A[i] * F[i]
        if current > x:
            cnt += -(-(current - x) // F[i])
            
    return cnt <= K

A.sort()
F.sort(reverse=True)
lb = 0
ub = 10 ** 12 + 1

while ub - lb > 1:
    mid = (lb + ub) // 2
    
    if ok(mid):
        ub = mid
    else:
        lb = mid
        
if sum(A) <= K:
    print(0)
else:
    print(ub)
Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect_left

N, *L= map(int, open(0).read().split())
X = sorted(L)
ans = 0
for i in range(N):
    for j in range(i + 1, N):
        lb = bisect_left(X[j + 1:], X[j] - X[i])
        ub = bisect_left(X[j + 1:], X[j] + X[i])
        ans += ub - lb
        
print(ans)



Fixed submission:
from bisect import bisect_left

N, *L= map(int, open(0).read().split())
X = sorted(L)
ans = 0
for i in range(N):
    for j in range(i + 1, N):
        ub = bisect_left(X, X[i] + X[j])
        ans += ub - (j + 1)
        
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N, M, L = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(M)]
Q = int(input())
X = [list(map(int, input().split())) for _ in range(Q)]

graph = [[float('inf')] * N for _ in range(N)]

for i in range(N):
    graph[i][i] = 0

for u, v, l in edges:
    graph[u - 1][v - 1] = l
    graph[v - 1][u - 1] = l

for k in range(N):
    for i in range(N):
        if graph[i][k] == float('inf'):
            continue
        for j in range(N):
            if graph[k][j] == float('inf'):
                continue
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

cnt = [[float('inf')] * N for _ in range(N)]

for i in range(N):
    cnt[i][i] = 0

for i in range(N):
    for j in range(N):
        if i == j:
            continue
        if graph[i][j] <= L:
            cnt[i][j] = 1
            cnt[j][i] = 1

for k in range(N):
    for i in range(N):
        if cnt[i][k] == float('inf'):
            continue
        for j in range(N):
            if cnt[k][j] == float('inf'):
                continue
            cnt[i][j] = min(cnt[i][j], cnt[i][k] + cnt[k][j])

for s, t in X:
    if cnt[s - 1][t - 1] == float('inf'):
        print(-1)
    else:
        print(cnt[s - 1][t - 1] - 1)



Fixed submission:
N, M, L = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(M)]
Q = int(input())
X = [list(map(int, input().split())) for _ in range(Q)]

INF = 10 ** 9 + 6
graph = [[INF] * N for _ in range(N)]

for i in range(N):
    graph[i][i] = 0

for u, v, l in edges:
    graph[u - 1][v - 1] = l
    graph[v - 1][u - 1] = l

for k in range(N):
    for i in range(N):
        if graph[i][k] == INF:
            continue
        for j in range(N):
            if graph[k][j] == INF:
                continue
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

cnt = [[INF] * N for _ in range(N)]

for i in range(N):
    cnt[i][i] = 0

for i in range(N):
    for j in range(N):
        if i == j:
            continue
        if graph[i][j] <= L:
            cnt[i][j] = 1
            cnt[j][i] = 1

for k in range(N):
    for i in range(N):
        if cnt[i][k] == INF:
            continue
        for j in range(N):
            if cnt[k][j] == INF:
                continue
            cnt[i][j] = min(cnt[i][j], cnt[i][k] + cnt[k][j])

for s, t in X:
    if cnt[s - 1][t - 1] == INF:
        print(-1)
    else:
        print(cnt[s - 1][t - 1] - 1)
Buggy python submission (verdict: Runtime Error):

A, B = map(int, input().split())

divisor = []
for i in range(1, int(A ** 0.5) + 1):
    if A % i == 0:
        divisor.append(i)
        if i != A // i:
            divisor.append(A // i)

divisor = sorted(v for v in divisor if B % v == 0)
lim = divisor[-1]
ok = [True] * (lim + 1)
ans = 0
for v in divisor:
    if ok[v]:
        ans += 1
        ok[v] = False
        if v != 1:
            for i in range(2 * v, lim + 1, v):
                ok[i] = False

print(ans)


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


def prime_factor(n):
    d = set()
    for i in range(2, n + 1):
        if i * i > n:
            break
        while n % i == 0:
            d.add(i)
            n //= i
            
    if n != 1:
        d.add(n)
    return d

a = prime_factor(A)
b = prime_factor(B)
print(len(set(a) & set(b)) + 1)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
print(sum(v for v in range(N)))


Fixed submission:
N = int(input())
print((N - 1) * N // 2)
Buggy python submission (verdict: Runtime Error):
N, Q = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(N - 1)]
P = [list(map(int, input().split())) for _ in range(Q)]

tree = [[] for _ in range(N + 1)]
for a, b in X:
    tree[a].append(b)

def dfs(u, x):
    ctr[u] += x
    for v in tree[u]:
        dfs(v, x)

ctr = [0] * (N + 1)
for p, x in P:
    dfs(p, x)
    
print(*ctr[1:])


Fixed submission:
from collections import deque

N, Q = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(N - 1)]
Y = [list(map(int, input().split())) for _ in range(Q)]

graph = [[] for _ in range(N + 1)]
for a, b in X:
    graph[a].append(b)
    graph[b].append(a)

ctr = [0] * (N + 1)
for p, x in Y:
    ctr[p] += x

# BFS
visited = [False] * (N + 1)
visited[1] = True
q = deque([1])
while q:
    u = q.popleft()
    for v in graph[u]:
        if visited[v]:
            continue
            
        ctr[v] += ctr[u]
        visited[v] = True
        q.append(v)
        
print(*ctr[1:])
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict
from bisect import bisect_left

s = input()
t = input()

indices = defaultdict(list)
for i, v in enumerate(s):
    indices[v].append(i)

cnt = 0
cur = -1
mod = len(s)
flag = False
for v in t:
    if v not in indices:
        flag = True
        break

    i = bisect_right(indices[v], cur)
    if i == len(indices[v]):
        j = indices[v][0]
    else:
        j = indices[v][i]

    if cur >= j:
        cnt += 1
    cur = j

if flag:
    print(-1)
else:
    print(cnt * mod + cur + 1)


Fixed submission:
from collections import defaultdict
from bisect import bisect_left

s = input()
t = input()

if set(s) >= set(t):
    d = defaultdict(list)
    for i, x in enumerate(s * 2):
        d[x].append(i)
    
    ans = 0
    cur = 0
    N = len(s)
    for x in t:
        cur_new = d[x][bisect_left(d[x], cur)]
        ans += cur_new - cur + 1
        cur = (cur_new + 1) % N

    print(ans)
else:
    print(-1)
Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappush, heappop
N, M = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(N)]

X.sort()
pq = []
ans = 0
for i in range(1, M + 1):
    while (len(X) > 0) and (X[0][0] <= i):
        heappush(pq, (-X[0][1]))
        X = X[1:]
    
    if pq:
        ans -= heappop(pq)
    
print(ans)




Fixed submission:
from heapq import heappush, heappop
from collections import defaultdict
N, M = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(N)]

cand = defaultdict(list)
for a, b in X:
    cand[a].append(b)

pq = []
ans = 0
for i in range(1, M + 1):
    for c in cand[i]:
        heappush(pq, -c)
    if pq:
        ans -= heappop(pq)
    
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
S = input()

MOD = 10 ** 9 + 7
MAX_LEN = len(S)
dp = [[0] * 13 for _ in range(MAX_LEN + 1)]
dp[0][0] = 1

for i in range(MAX_LEN):
    c = int(S[i]) if S[i] != '?' else -1
    for j in range(10):
        if c != -1 and c != j:
            continue
        
        for k in range(13):
            dp[i + 1][(k * 10 + j) % 13] += dp[i][k]
            
    for j in range(10):
        dp[i + 1][j] %= MOD
        
print(dp[-1][5])


Fixed submission:
S = input()

MOD = 10 ** 9 + 7
MAX_LEN = len(S)
dp = [[0] * 13 for _ in range(MAX_LEN + 1)]
dp[0][0] = 1

for i in range(MAX_LEN):
    c = int(S[i]) if S[i] != '?' else -1
    for j in range(10):
        if c != -1 and c != j:
            continue
        
        for k in range(13):
            idx = (k * 10 + j) % 13
            dp[i + 1][idx] += dp[i][k]
            dp[i + 1][idx] %= MOD
        
print(dp[-1][5])
Buggy python submission (verdict: Time Limit Exceeded):
s = input()
t = input()

def z_algorithm(s):
    n = len(s)
    res = [0] * n
    i = 1
    j = 0
    while i < n:
        # i番目以降の一致文字数
        while i + j < n and s[j] == s[i + j]:
            j += 1
        res[i] = j

        # 一文字も一致しない場合，次の文字へ
        if j == 0:
            i += 1
            continue

        # 一致したところまでを埋める
        k = 1
        while i + k < n and k + res[k] < j:
            res[i + k] = res[k]
            k += 1
        
        i += k
        j -= k
        
    return res


n = len(t)
ss = s
while len(ss) < n:
    ss += s
ss += s

z = z_algorithm(t + ss * 2)
z = [min(z[i], n) for i in range(n, len(z))]

ans = 0
for i in range(n):
    c = 0
    for v in z[i::n]:
        if v == n:
            c += 1
        else:
            c = 0
        ans = max(ans, c)
        
if ans <= len(ss) // n:
    print(ans)
else:
    print(-1)


Fixed submission:
s = input()
t = input()

def z_algorithm(s):
    n = len(s)
    res = [0] * n
    i = 1
    j = 0
    while i < n:
        # i番目以降の一致文字数
        while i + j < n and s[j] == s[i + j]:
            j += 1
        res[i] = j

        # 一文字も一致しない場合，次の文字へ
        if j == 0:
            i += 1
            continue

        # 一致したところまでを埋める
        k = 1
        while i + k < n and k + res[k] < j:
            res[i + k] = res[k]
            k += 1
        
        i += k
        j -= k
        
    return res


n = len(t)
if n > len(s):
    ss = s * (n // len(s) + 2)
else:
    ss = s * 2

z = z_algorithm(t + ss * 2)
z = [min(z[i], n) for i in range(n, len(z))]

ans = 0
for i in range(n):
    c = 0
    for v in z[i::n]:
        if v == n:
            c += 1
        else:
            c = 0
        ans = max(ans, c)
        
if ans <= len(ss) // n:
    print(ans)
else:
    print(-1)
Buggy python submission (verdict: Runtime Error):
from bisect import bisect_left
N, *A = map(int, open(0).read().split())

INF = 10 ** 6
dp = [INF] * (N + 1)
ans = 0
for i in range(N):
    idx = bisect_left(dp, A[i])
    dp[idx] = A[i]
    ans += 1 if idx == 0 else 0
print(ans)

Fixed submission:
from bisect import bisect
N, *A = map(int, open(0).read().split())

INF = 10 ** 9 + 7
dp = [INF] * (N + 1)
for i in range(N):
    dp[bisect(dp, -A[i])] = -A[i]

print(sum(dp[i] < INF for i in range(N)))