Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
s = list(input())
p = int(input())
dir = 0
for _ in range(p):
  Q = input().split()
  if Q[0] == "1":
    dir = not dir
  else:
    if (int(Q[1]) - 1) == dir:
      s.insert(0, Q[2])
    else:
      s.append(Q[2])
      
if not dir:
  print("".join(s))
else:
  print("".join(s[::-1]))  

Fixed submission:
from collections import deque
S = list(input())
q = int(input())
Q = [list(input().split()) for _ in range(q)]

ds = deque(S)

flg = True
for i in Q:
  if i[0] == "1":
    flg = not flg
  else:
    if flg == True:
      if i[1] == "1":
        ds.appendleft(i[2])
      else:
        ds.append(i[2])
    else:
      if i[1] == "2":
        ds.appendleft(i[2])
      else:
        ds.append(i[2])
if flg:
  print("".join(ds))
else:
  print("".join(ds)[::-1])

Buggy python submission (verdict: Time Limit Exceeded):
S = input()
q = int(input())
Q = [list(input().split()) for _ in range(q)]

flg = True
for i in Q:
  if i[0] == "1":
    flg = not flg
  else:
    if flg == True:
      if i[1] == "1":
        S = i[2] + S
      else:
        S = S + i[2]
    else:
      if i[1] == "2":
        S = i[2] + S
      else:
        S = S + i[2]
if flg:
  print(S)
else:
  print(S[::-1])

        

Fixed submission:
from collections import deque
S = list(input())
q = int(input())
Q = [list(input().split()) for _ in range(q)]

ds = deque(S)

flg = True
for i in Q:
  if i[0] == "1":
    flg = not flg
  else:
    if flg == True:
      if i[1] == "1":
        ds.appendleft(i[2])
      else:
        ds.append(i[2])
    else:
      if i[1] == "2":
        ds.appendleft(i[2])
      else:
        ds.append(i[2])
if flg:
  print("".join(ds))
else:
  print("".join(ds)[::-1])
Buggy python submission (verdict: Time Limit Exceeded):
n, p = map(int, input().split())
S = list(map(int, list(input())))

if p == 2 or p == 5:
  ans = 0
  for i, x in enumerate(S[::-1]):
    if x % p == 0:
      ans += n - i
else:
  mods = [0 for _ in range(p)]
  mods[0] = 1

  num = 0
  digit = 1
  for s in S[::-1]:
    num = (s * digit + num) % p
    mods[num] += 1
    digit = digit * 10
  
  ans = 0
  for m in mods:
    ans += m * (m - 1) // 2

print(ans)


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

if p == 2 or p == 5:
  ans = 0
  for i, x in enumerate(S[::-1]):
    if x % p == 0:
      ans += n - i
else:
  mods = [0 for _ in range(p)]
  mods[0] = 1

  num = 0
  digit = 1
  for s in S[::-1]:
    num = (s * digit + num) % p
    mods[num] += 1
    digit = (digit * 10) % p
  
  ans = 0
  for m in mods:
    ans += m * (m - 1) // 2

print(ans)

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

if p == 2 or p == 5:
  ans = 0
  for i, x in enumerate(S[::-1]):
    if x % p == 0:
      ans += n - i
else:
  mods = [0 for _ in range(p)]
  mods[0] = 1

  num = 0
  digit = 1
  for s in S[::-1]:
    num = (s * digit + num) % p
    mods[num] += 1
    digit = digit * 10
  
  ans = 0
  for m in mods:
    ans += m * (m - 1) // 2

print(ans)


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

if p == 2 or p == 5:
  ans = 0
  for i, x in enumerate(S[::-1]):
    if x % p == 0:
      ans += n - i
else:
  mods = [0 for _ in range(p)]
  mods[0] = 1

  num = 0
  digit = 1
  for s in S[::-1]:
    num = (s * digit + num) % p
    mods[num] += 1
    digit = (digit * 10) % p
  
  ans = 0
  for m in mods:
    ans += m * (m - 1) // 2

print(ans)

Buggy python submission (verdict: Runtime Error):
n, p = map(int, input().split())
S = list(map(int, list(input())))

MOD = p

mods = [0 for _ in range(2019)]
mods[0] = 1

num = 0
digit = 1
for s in S[::-1]:
  num = s * digit + num
  num %= MOD
  mods[num] += 1
  digit = (digit * 10) % MOD
  
ans = 0
for m in mods:
  ans += m * (m - 1) // 2

print(ans)


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

if p == 2 or p == 5:
  ans = 0
  for i, x in enumerate(S[::-1]):
    if x % p == 0:
      ans += n - i
else:
  mods = [0 for _ in range(p)]
  mods[0] = 1

  num = 0
  digit = 1
  for s in S[::-1]:
    num = (s * digit + num) % p
    mods[num] += 1
    digit = (digit * 10) % p
  
  ans = 0
  for m in mods:
    ans += m * (m - 1) // 2

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect_left, bisect_right

N = int(input())
S = list(input())
Q = int(input())

D = {chr(ord('a') + i): [] for i in range(26)}

for i, s in enumerate(S):
    D[s].append(i)

for q in range(Q):
    query = list(input().split())
    if query[0] == '1':
        i, x = int(query[1]), query[2]
        i -= 1
        s = S[i]
        if s == x:
            continue

        D[s].remove(i)
        next_i = bisect_left(D[x], i)
        D[x].insert(next_i, i)
        S[i] = x

    if query[0] == '2':
        l, r = int(query[1]), int(query[2])
        l, r = l - 1, r - 1
        ans = 0
        for i in range(26):
            s = chr(ord('a') + i)

            li = bisect_left(D[s], l)
            ri = bisect_right(D[s], r)

            if ri - li > 0:
                ans += 1

        print(ans)

Fixed submission:
from bisect import bisect_left, bisect_right

N = int(input())
S = list(input())
Q = int(input())

D = {chr(ord('a') + i): [] for i in range(26)}

for i, s in enumerate(S):
    D[s].append(i)

for q in range(Q):
    query = list(input().split())
    if query[0] == '1':
        i, x = int(query[1]), query[2]
        i -= 1
        s = S[i]
        if s == x:
            continue

        D[s].remove(i)
        next_i = bisect_left(D[x], i)
        D[x].insert(next_i, i)
        S[i] = x

    if query[0] == '2':
        l, r = int(query[1]), int(query[2])
        l, r = l - 1, r - 1
        ans = 0
        for i in range(26):
            s = chr(ord('a') + i)

            li = bisect_left(D[s], l)
            ri = bisect_right(D[s], r)

            if ri - li > 0:
                ans += 1

        print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from functools import lru_cache

def framod(n, mod, a=1):
    for i in range(1,n+1):
        a=a * i % mod
    return a

def power(n, r, mod):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod

def comb(n, k, mod):
    a=framod(n, mod)
    b=framod(k, mod)
    c=framod(n-k, mod)
    return (a * power(b, mod-2, mod) * power(c, mod-2, mod)) % mod

n, a, b = map(int, input().split())
MOD = 10 ** 9 + 7

# ans = power(2, n, MOD) - 1 - (power(2, a, MOD) - power(2, a - 1, MOD)) - (power(2, b, MOD) - power(2, b - 1, MOD))
ans = power(2, n, MOD) - 1 - comb(n, a, MOD) - comb(n, b, MOD)
# - comb(2, a, MOD) - comb(2, b, MOD)

print(ans % MOD)

Fixed submission:
def power(n, r, mod):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod

def comb(n,k,mod):
    if n<k:
        return 0
    if n<0 or k<0:
        return 0
    k=min(n-k,k)
    ans=1
    inv=[1]*(k+1)
    if k>=1:
        ans*=(n-k+1)%mod
    for i in range(2,k+1):
        inv[i]=mod-inv[mod%i]*(mod//i)%mod
        ans=ans*(n-k+i)*inv[i]%mod
    return ans

n, a, b = map(int, input().split())
MOD = 10 ** 9 + 7

ans = power(2, n, MOD) - 1 - comb(n, a, MOD) - comb(n, b, MOD)

print(ans % MOD)
Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10 ** 6)

from math import factorial
def comb(n, r):
  if r < 0 or r > n:
    return 0
  else:
    return factorial(n) // (factorial(n - r) * factorial(r))

# 左から i 桁目以降について、0 以外の値を残り K 個使用可能
# smaller: i 桁目までが 一致している時=False, 小さい時=True  
def solve(i, k, smaller):
  if i == n:
    if k == 0:
      return 1
    else:
      return 0
  if k == 0:
    return 1
  if smaller:
    return comb(n - i, k) * 9 ** k
  else:
    if S[i] == "0":
      return solve(i + 1, k, Flase)
    else:
      zero = solve(i + 1, k, True)
      aida = solve(i + 1, k - 1, True) * (int(S[i]) - 1)
      icchi = solve(i + 1, k - 1, False)
      return zero + aida + icchi

S = input()  
n = len(S)
k = int(input())
print(solve(0, k, False))

Fixed submission:
import sys
sys.setrecursionlimit(10 ** 6)

from math import factorial
def comb(n, r):
  if r < 0 or r > n:
    return 0
  else:
    return factorial(n) // (factorial(n - r) * factorial(r))

# 左から i 桁目以降について、0 以外の値を残り K 個使用可能
# smaller: i 桁目までが 一致している時=False, 小さい時=True  
def solve(i, k, smaller):
  if i == n:
    if k == 0:
      return 1
    else:
      return 0
  if k == 0:
    return 1
  if smaller:
    return comb(n - i, k) * 9 ** k
  else:
    if S[i] == "0":
      return solve(i + 1, k, False)
    else:
      zero = solve(i + 1, k, True)
      aida = solve(i + 1, k - 1, True) * (int(S[i]) - 1)
      icchi = solve(i + 1, k - 1, False)
      return zero + aida + icchi

S = input()  
n = len(S)
k = int(input())
print(solve(0, k, False))

Buggy python submission (verdict: Runtime Error):
from math import factorial
def comb(n, r):
  if r < 0 or r > n:
    return 0
  else:
    return factorial(n) // (factorial(n - r) * factorial(r))

# 左から i 桁目以降について、0 以外の値を残り K 個使用可能
# smaller: i 桁目までが 一致している時=False, 小さい時=True  
def solve(i, k, smaller):
  if i == n:
    if k == 0:
      return 1
    else:
      return 0
  if k == 0:
    return 1
  if smaller:
    return comb(n - i, k) * 9 ** k
  else:
    if S[i] == "0":
      return solve(i + 1, k, Flase)
    else:
      zero = solve(i + 1, k, True)
      aida = solve(i + 1, k - 1, True) * (int(S[i]) - 1)
      icchi = solve(i + 1, k - 1, False)
      return zero + aida + icchi

S = input()  
n = len(S)
k = int(input())
print(solve(0, k, False))

Fixed submission:
import sys
sys.setrecursionlimit(10 ** 6)

from math import factorial
def comb(n, r):
  if r < 0 or r > n:
    return 0
  else:
    return factorial(n) // (factorial(n - r) * factorial(r))

# 左から i 桁目以降について、0 以外の値を残り K 個使用可能
# smaller: i 桁目までが 一致している時=False, 小さい時=True  
def solve(i, k, smaller):
  if i == n:
    if k == 0:
      return 1
    else:
      return 0
  if k == 0:
    return 1
  if smaller:
    return comb(n - i, k) * 9 ** k
  else:
    if S[i] == "0":
      return solve(i + 1, k, False)
    else:
      zero = solve(i + 1, k, True)
      aida = solve(i + 1, k - 1, True) * (int(S[i]) - 1)
      icchi = solve(i + 1, k - 1, False)
      return zero + aida + icchi

S = input()  
n = len(S)
k = int(input())
print(solve(0, k, False))
Buggy python submission (verdict: Time Limit Exceeded):
h, n = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(n)]
MOD = 10 ** 18
D = [MOD] * (h + 10 ** 4)
D[0] = 0
 
for i in range(h):
    for a, b in AB:
        D[i + a] = min(D[i + a], D[i] + b)
print(min(D[h:]))

Fixed submission:
h, n = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(n)]
MOD = 10 ** 18
D = [MOD] * (h + 10 ** 4)
D[0] = 0
 
for i in range(h):
    for a, b in AB:
        D[i + a] = min(D[i + a], D[i] + b)
print(min(D[h:]))
Buggy python submission (verdict: Runtime Error):
# C - Snack
# https://atcoder.jp/contests/abc148/tasks/abc148_c

from math import gcd

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

a, b = map(int, input().split())
print(lcm(a, b))

Fixed submission:
from fractions import gcd

# 最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

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

ans = lcm(A, B)

print(ans)
Buggy python submission (verdict: Runtime Error):
ERGTHJKJKJREbv ffffffs bboiuyazxcvbnm,.,mnbvcvbnjmk,l.kjhgfxzxcbnbvcxzxcvbgvcx

Fixed submission:
suma = sum(list(map(int, input().split())))
if suma >= 22:
  print("bust")
else:
  print("win")
Buggy python submission (verdict: Time Limit Exceeded):
def sumXOR(arr, n):       
    MOD = 10 ** 9 + 7
    sum = 0
    for i in range(0, 61): 
        zc = 0
        oc = 0
        idsum = 0
        for j in range(0, n): 
            if (arr[j] % 2 == 0): 
                zc = zc + 1                  
            else: 
                oc = oc + 1
            arr[j] = arr[j] // 2 
          
        idsum = oc * zc * (1 << i)    
        sum = (sum + idsum) % MOD;        
    return sum

n = int(input())
A = list(map(int, input().split()))
sum = 0
sum = sumXOR(A, n); 
print(sum) 


Fixed submission:
def sumXOR(arr, n):       
    MOD = 10 ** 9 + 7
    sum = 0
    for i in range(0, 61): 
        zc = 0
        oc = 0
        idsum = 0
        for j in range(0, n): 
            if (arr[j] % 2 == 0): 
                zc = zc + 1                  
            else: 
                oc = oc + 1
            arr[j] = arr[j] // 2 
          
        idsum = oc * zc * (1 << i)    
        sum = (sum + idsum) % MOD;        
    return sum

n = int(input())
A = list(map(int, input().split()))
sum = 0
sum = sumXOR(A, n); 
print(sum)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = list(map(int, list(input())))

ans = set()
for i in range(10):
  for j in range(10):
    for k in range(10):
      iflg = False
      jflg = False
      for s in S:
        if not iflg and s == i:
          iflg = True
        elif (not jflg) and iflg and s == j:
          jflg = True
          continue
        elif iflg and jflg and s == k:
          ans.add((i,j,k))
          break
print(len(ans))

Fixed submission:
N = int(input())
S = list(map(int, list(input())))

ans = set()
for i in range(10):
  for j in range(10):
    for k in range(10):
      iflg = False
      jflg = False
      for s in S:
        if not iflg and s == i:
          iflg = True
        elif (not jflg) and iflg and s == j:
          jflg = True
          continue
        elif iflg and jflg and s == k:
          ans.add((i,j,k))
          break
print(len(ans))

Buggy python submission (verdict: Time Limit Exceeded):
from itertools import combinations
N = int(input())
S = list(map(int, list(input())))

print(len(set(combinations(S,3))))

Fixed submission:
N = int(input())
S = list(map(int, list(input())))

ans = set()
for i in range(10):
  for j in range(10):
    for k in range(10):
      iflg = False
      jflg = False
      for s in S:
        if not iflg and s == i:
          iflg = True
        elif (not jflg) and iflg and s == j:
          jflg = True
          continue
        elif iflg and jflg and s == k:
          ans.add((i,j,k))
          break
print(len(ans))
Buggy python submission (verdict: Time Limit Exceeded):
T1, T2 = map(int, input().split())
A1, A2 = map(int, input().split())
B1, B2 = map(int, input().split())

D1 = T1 * (A1 - B1)
D2 = T2 * (A2 - B2)
li = [D1, D2]
li.sort()

pos = 0
cnt = 0
for _ in range(10000000):
  pos += li[0]
  pos1 = pos
  pos += li[1]
  pos2 = pos
  if pos1 < 0 and pos2 >= 0:
    cnt += 2
if cnt >= 1000000:
  print("infinity")
else:
  print(cnt-1)

Fixed submission:
t1, t2 = map(int, input().split())
a1, a2 = map(int, input().split())
b1, b2 = map(int, input().split())

if ((a1 - b1) * (a2 - b2) > 0) or (abs(a1 - b1) * t1 > abs(a2 - b2) * t2):
  print(0)
elif abs(a1 - b1) * t1 == abs(a2 - b2) * t2:
  print("infinity")
else:
  d, m = divmod(abs(a1 - b1) * t1, abs(a2 - b2) * t2 - abs(a1 - b1) * t1)
  ans = d * 2
  if m > 0:
    ans += 1
  print(ans)
Buggy python submission (verdict: Runtime Error):
X, Y = map(int, input().split())
def framod(n, mod, a=1):
    for i in range(1,n+1):
        a=a * i % mod
    return a

def power(n, r, mod):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod

def comb(n, k, mod):
    a=framod(n, mod)
    b=framod(k, mod)
    c=framod(n-k, mod)
    return (a * power(b, mod-2, mod) * power(c, mod-2, mod)) % mod
mod = 10 ** 9 + 7
  
if (X + Y) % 3 == 0:
  n = (X + Y) // 3 
  if min(X, Y) >= n:
    s = min(X, Y) - n
    ans = comb(n, s, mod)
else:
  ans = 0

print(ans)


Fixed submission:
X, Y = map(int, input().split())
def framod(n, mod, a=1):
    for i in range(1,n+1):
        a=a * i % mod
    return a

def power(n, r, mod):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod

def comb(n, k, mod):
    a=framod(n, mod)
    b=framod(k, mod)
    c=framod(n-k, mod)
    return (a * power(b, mod-2, mod) * power(c, mod-2, mod)) % mod
  
mod = 10 ** 9 + 7
  
if (X + Y) % 3 == 0:
  n = (X + Y) // 3 
  if min(X, Y) >= n:
    s = min(X, Y) - n
    ans = comb(n, s, mod)
  else:
    ans = 0
else:
  ans = 0

print(ans)

Buggy python submission (verdict: Runtime Error):
X, Y = map(int, input().split())

def comb(n, k, p):
  # nCk mod p (組合せのmod)
  from math import factorial
  if n < 0 or k < 0 or n < k:
    return 0
  if n == 0 or k == 0:
    return 1
  a = factorial(n) % p
  b = factorial(k) % p
  c = factorial(n - k) % p
  return (a * power_func(b, p - 2, p) * power_func(c, p - 2, p)) % p

def power_func(a, b, p):
  # a ^ b mod p # (指数のmod)
  if b == 0:
    return 1
  if b % 2 == 0:
    d = power_func(a, b // 2, p)
    return d * d % p
  if b % 2 == 1:
    return (a * power_func(a, b - 1, p )) % p

mod = 10 ** 9 + 7
  
if (X + Y) % 3 == 0:
  n = (X + Y) // 3 
  if min(X, Y) >= n:
    s = min(X, Y) - n
    ans = comb(n, s, mod)
else:
  ans = 0

print(ans)


Fixed submission:
X, Y = map(int, input().split())
def framod(n, mod, a=1):
    for i in range(1,n+1):
        a=a * i % mod
    return a

def power(n, r, mod):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod

def comb(n, k, mod):
    a=framod(n, mod)
    b=framod(k, mod)
    c=framod(n-k, mod)
    return (a * power(b, mod-2, mod) * power(c, mod-2, mod)) % mod
  
mod = 10 ** 9 + 7
  
if (X + Y) % 3 == 0:
  n = (X + Y) // 3 
  if min(X, Y) >= n:
    s = min(X, Y) - n
    ans = comb(n, s, mod)
  else:
    ans = 0
else:
  ans = 0

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))
A.sort()
F.sort(reverse=True)
l = -1
r = 10 ** 13
while r - l > 1:
  m = (l + r) // 2
  if sum([(a - m // f) if a * f > m else 0 for a, f in zip(A, F)]) <= k:
    r = m
  else:
    l = m
    
print(r)

Fixed submission:
n, k = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))
A.sort()
F.sort(reverse=True)
l = -1
r = 10 ** 13
while r - l > 1:
  m = (l + r) // 2
  if sum([(a - m // f) if a * f > m else 0 for a, f in zip(A, F)]) <= k:
    r = m
  else:
    l = m
    
print(r)
Buggy python submission (verdict: Time Limit Exceeded):
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

#N = int(input())
#L = list(map(int, input().split()))
N = 7

i = "218 786 704 233 645 728 389"
L = list(map(int, i.split()))



L.sort()

print(L)

l1 = 0
l2 = 1
l3 = 2
ans = 0
while l1 < N - 2:
    while l3 < N: 
      if L[l1] + L[l2] > L[l3]:
        l3 += 1
      else:
        ans += cmb(l3 - l1 + 1, 3) 
        l2 = l3 - 1
        l1 = l2 - 1
  
      if l3 == l2 + 1 and l2 == l1 + 1: 
        l3 += 1
      elif l2 == l1 + 1:
        l2 += 1
      else:
        l1 += 1

print(ans)

Fixed submission:
import bisect

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

L.sort()

ans = 0
for i in range(N-2):
  for j in range(i + 1, N-1):
    idx = bisect.bisect_left(L, L[i] + L[j]) - 1
    ans += idx - j

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
# 長さNの文字列Sについて、i=2,3,...,N でのSのi文字目以降から成る文字列とSの最長共通接頭辞の長さ O(N) 
def z_algo(S):
    n = len(S)
    LCP = [0]*n
    i = 1
    j = 0
    c = 0 #最も末尾側までLCPを求めたインデックス
    for i in range(1, n):
        #i番目からのLCPが以前計算したcからのLCPに含まれている場合
        if i+LCP[i-c] < c+LCP[c]:
            LCP[i] = LCP[i-c]
        else:
            j = max(0, c+LCP[c]-i)
            while i+j < n and S[j] == S[i+j]: j+=1
            LCP[i] = j
            c = i
    LCP[0] = n
    return LCP
  
N = int(input())
S = input()

ans = 0
for i in range(N):
  SS = S[i:]
  lcp = z_algo(SS)
  for j in range(len(lcp)):
    l = min(lcp[j], j)
    ans = max(ans, l)

print(ans)

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

l = 0
r = 1
ans = 0
# 順番に見ていく

while r < n:
  if s[l:r] in s[r:]:
    ans = max(ans, r - l)
    r += 1
  else:
    l += 1
  if l == r:
    l += 1
    r += 2
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
# 長さNの文字列Sについて、i=2,3,...,N でのSのi文字目以降から成る文字列とSの最長共通接頭辞の長さ O(N) 
def z_algo(S):
    N = len(S)
    A = [0]*N
    i = 1; j = 0
    A[0] = l = len(S)
    while i < l:
        while i+j < l and S[j] == S[i+j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while l-i > k < j - A[k]:
            A[i+k] = A[k]
            k += 1
        i += k; j -= k
    return A
  
N = int(input())
S = input()

ans = 0
for i in range(N):
  SS = S[i:]
  lcp = z_algo(SS)
  for j in range(len(lcp)):
    l = min(lcp[j], j)
    ans = max(ans, l)

print(ans)

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

l = 0
r = 1
ans = 0
# 順番に見ていく

while r < n:
  if s[l:r] in s[r:]:
    ans = max(ans, r - l)
    r += 1
  else:
    l += 1
  if l == r:
    l += 1
    r += 2
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
input()
s = input()
ls = list(s)
cols = Counter(ls)
# ２個以上ある文字のリスト作成
dbls =[]
for k, v in cols.items():
  if v >= 2:
    dbls.append(k)

left = 0
right = 0
word = ""
ans = 0
# 順番に見ていく

while right < len(s):
  if s[right] in dbls:
    word += s[right]
    if s[right+1:].find(word) >= 0:
      ans = max(ans, len(word))
      right += 1
    else:
      word = ""
#      left = max(left + 1, right)
      left += 1
      right = left
  else:
    word = ""
#    left = max(left + 1, right)
    left += 1
    right = left

print(ans)

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

l = 0
r = 1
ans = 0
# 順番に見ていく

while r < n:
  if s[l:r] in s[r:]:
    ans = max(ans, r - l)
    r += 1
  else:
    l += 1
  if l == r:
    l += 1
    r += 2
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
A = [i for i in range(1, n + 1)]
B = [n] + [i for i in range(1, n)]
ans = sum(i % j for i, j in zip(B, A))
print(ans)

Fixed submission:
n = int(input())
print((n*(n-1))//2)
Buggy python submission (verdict: Time Limit Exceeded):
n, q = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n - 1)]
px = [list(map(int, input().split())) for _ in range(q)]
ab.sort(key=lambda x: (x[0], x[1]))
px.sort(key=lambda x: (x[0], x[1]))
ans = [0] * n

for i in px:
  ans[i[0] - 1] += i[1]

for i in ab:
  ans[i[1] - 1] += ans[i[0] - 1]
  
print(*ans)

Fixed submission:
n, q = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n - 1)]
px = [list(map(int, input().split())) for _ in range(q)]
ab.sort(key=lambda x: x[0])
ans = [0] * n

for i in px:
  ans[i[0] - 1] += i[1]

for i in ab:
  ans[i[1] - 1] += ans[i[0] - 1]
  
print(*ans)
Buggy python submission (verdict: Runtime Error):
import heapq

N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
ABS = sorted(AB, key=lambda x: -x[1])
ABSS = sorted(ABS, key=lambda x: x[0])
# print(ABS)
# print(ABSS)

heap = []
ans = 0
chkpos = 0

for i in range(1, M+1):
  while ABSS[chkpos][0] <= i:
    heapq.heappush(heap, -1 * ABSS[chkpos][1])
    chkpos += 1
    if chkpos >= N -1:
      break
#  print(heap)
  if len(heap) > 0:
    ans -= heapq.heappop(heap)
print(ans)

Fixed submission:
import heapq

N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
ABS = sorted(AB, key=lambda x: -x[1])
ABSS = sorted(ABS, key=lambda x: x[0])
# print(ABS)
# print(ABSS)

heap = []
ans = 0
chkpos = 0

for i in range(1, M + 1):
  if chkpos < N:
    while ABSS[chkpos][0] <= i:
  #    print(chkpos, len(ABSS))
      heapq.heappush(heap, -1 * ABSS[chkpos][1])
      chkpos += 1
      if chkpos >= N:
        break
  #  print(heap)
    if len(heap) > 0:
      ans -= heapq.heappop(heap)
  else:
    ans -= heapq.heappop(heap)
print(ans)