Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
L = list(map(int, input().split()))
L.sort()
L.append(2*10**3)
 
c = 0
for i in range(N-2):
  for j in range(i+1, N-1):
    kl, kr = j, N+1
    km = (kl + kr) // 2
    li, lj = L[i], L[j]
    while kr > kl+1:
      if L[km] < li + lj:
        kl = km
      else:
        kr = km
      
      km = (kl + kr) // 2
    
    if L[kr] < li + lj:
      c += kr - j
    else:
      c += kl - j

print(c)

Fixed submission:
import bisect

N = int(input())
L = list(map(int, input().split()))
L.sort()
 
c = 0
for i in range(N-2):
  for j in range(i+1, N-1):
    c += bisect.bisect_right(L, L[i]+L[j]-1) - j - 1


print(c)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
L = list(map(int, input().split()))
L.sort()

c = 0
for i in range(N):
  for j in range(i+1, N):
    for k in range(j+1, N):
      if L[k]<L[i]+L[j]:
        c += 1
      
      else:
        break

print(c)

Fixed submission:
import bisect

N = int(input())
L = list(map(int, input().split()))
L.sort()
 
c = 0
for i in range(N-2):
  for j in range(i+1, N-1):
    c += bisect.bisect_right(L, L[i]+L[j]-1) - j - 1


print(c)
Buggy python submission (verdict: Time Limit Exceeded):
def warshall_floyd(d):
  n = len(d)
  for i in range(n):
    for j in range(n):
      for k in range(n):
        d[j][k] = min(d[j][k], d[j][i]+d[k][i])
  
  return d


N, M, L = map(int, input().split())
d = [[float('inf') for _ in range(N)] for _ in range(N)]

for _ in range(M):
  a, b, c = map(int, input().split())
  d[a-1][b-1] = c
  d[b-1][a-1] = c
  
for i in range(N):
  d[i][i] = 0

d = warshall_floyd(d)
d2 = [[1 if d[i][j]<=L else float('inf') for j in range(N)] for i in range(N)]
for i in range(N):
  d2[i][i] = 0

d2 = warshall_floyd(d2)

Q = int(input())
for _ in range(Q):
  s, t = map(int, input().split())
  out = d2[s-1][t-1]
  print(-1 if out == float('inf') else int(out-1))

Fixed submission:
from scipy.sparse.csgraph import floyd_warshall
import numpy as np

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

D = np.ones([N, N]) * np.inf
D[np.eye(N, dtype=bool)] = 0

for _ in range(M):
  A, B, C = map(int, input().split())
  D[A-1, B-1] = C
  D[B-1, A-1] = C

D = floyd_warshall(D)
D2 = D <= L

D2 = floyd_warshall(D2)

Q = int(input())
for _ in range(Q):
  s, t = map(int, input().split())
  r = D2[s-1, t-1] - 1
  if r < np.inf:
    print(int(r))
  else:
    print(-1)

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

def warshall_floyd(d):
  n = len(d)
  for i in range(n):
    for j in range(n):
      for k in range(n):
        d[j, k] = min(d[j, k], d[j, i]+d[k, i])
  
  return d


N, M, L = map(int, input().split())
d = np.ones([N, N]) * np.inf

for _ in range(M):
  a, b, c = map(int, input().split())
  d[a-1, b-1] = c
  d[b-1, a-1] = c
  
for i in range(N):
  d[i, i] = 0

d = warshall_floyd(d)
d2 = (d <= L)*1.0
d2[d2 == 0] = np.inf
d2 = warshall_floyd(d2)

Q = int(input())
for _ in range(Q):
  s, t = map(int, input().split())
  out = d2[s-1, t-1]
  print(-1 if out == np.inf else int(out-1))
  

Fixed submission:
from scipy.sparse.csgraph import floyd_warshall
import numpy as np

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

D = np.ones([N, N]) * np.inf
D[np.eye(N, dtype=bool)] = 0

for _ in range(M):
  A, B, C = map(int, input().split())
  D[A-1, B-1] = C
  D[B-1, A-1] = C

D = floyd_warshall(D)
D2 = D <= L

D2 = floyd_warshall(D2)

Q = int(input())
for _ in range(Q):
  s, t = map(int, input().split())
  r = D2[s-1, t-1] - 1
  if r < np.inf:
    print(int(r))
  else:
    print(-1)
Buggy python submission (verdict: Runtime Error):
S = list(input())
K = int(input())

ans = 0
for i in range(1, len(S)):
  pre_s = S[i-1]
  s = S[i]
  if s == pre_s:
    S[i] = '#'
    ans += 1

if S[1] == '#' and len(S) >= 3 and S[0] != S[2]:
  S[0], S[1] = S[1], S[0]

ans *= K
if S[0] == S[-1]:
  ans += K - 1

print(ans)

Fixed submission:
S = list(input())
N = len(S)
K = int(input())
if N == 1:
  print(K//2)
  quit()

S = S + S + S
ans_first = ans_odd = ans_even = 0
for i in range(1, N):
  pre_s = S[i-1]
  s = S[i]
  if s == pre_s:
    ans_first += 1
    S[i] = '#'

for i in range(N, 2*N):
  pre_s = S[i-1]
  s = S[i]
  if s == pre_s:
    ans_even += 1
    S[i] = '#'

for i in range(2*N, 3*N):
  pre_s = S[i-1]
  s = S[i]
  if s == pre_s:
    ans_odd += 1
    S[i] = '#'

k_even = K // 2
k_odd = K - k_even - 1
print(ans_first + k_odd*ans_odd + k_even*ans_even)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))

print(*[A.index(i)+1 for i in range(1, N+1)])

Fixed submission:
import numpy as np

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

print(*np.argsort(A)+1)
Buggy python submission (verdict: Time Limit Exceeded):
INF = 10**8

N, M = map(int, input().split())
n = 2 ** N
dp = [0] + [INF]*(n - 1)

for _ in range(M):
  a, b = map(int, input().split())
  c = sum(map(lambda x:2**(x-1), list(map(int, input().split()))))
  for i in range(n):
    dp[i | c] = min(dp[i] + a, dp[i | c])
  
if dp[-1] == INF:
  print(-1)
else:
  print(dp[-1])

Fixed submission:
INF = 10**8

N, M = map(int, input().split())
n = 2 ** N
dp = [0] + [INF]*(n - 1)

for _ in range(M):
  a, b = map(int, input().split())
  c = sum(map(lambda x:2**(x-1), list(map(int, input().split()))))
  for i in range(n):
    dp[i | c] = min(dp[i] + a, dp[i | c])
  
if dp[-1] == INF:
  print(-1)
else:
  print(dp[-1])
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np

H, W, A, B = map(int, input().split())
ans = np.zeros([H, W], dtype=int)
ans[:B, :A] = ans[B:, A:] = 1

for a in ans:
  print(*a, sep='')

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

ans = [['1' if (h<B and w<A) or (B<=h and A<=w) else '0' for w in range(W)] for h in range(H)]

for a in ans:
  print(''.join(a))
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np

N, K, Q = list(map(int, input().split()))

A_point = np.array([K] * N)

for _ in range(Q):
  a = int(input())
  A_point[a-1] += 1
  A_point -= 1

for i in range(N):
  if A_point[i] > 0:
    print('Yes')
  else:
    print('No')  

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

A_point = [K] * N

for _ in range(Q):
  A_point[int(input())-1] += 1

A_point = map(lambda x:x-Q, A_point)

for r in A_point:
  if r > 0:
    print('Yes')
  else:
    print('No')
Buggy python submission (verdict: Time Limit Exceeded):
N, M = list(map(int, input().split()))
A = list(map(int, input().split()))

for _ in range(M):
  m = max(A)
  A[A.index(m)] = m // 2

print(sum(A))

Fixed submission:
import heapq

N, M = map(int, input().split())
A = list(map(int, input().split()))
A = list(map(lambda x:-x, A))

heapq.heapify(A)

for _ in range(M):
  a = -heapq.heappop(A)
  heapq.heappush(A, -(a//2))

print(-sum(A))
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = input()

ans = 0
for i in range(N):
  j_start = ans + 1
  j_end = (N - i) // 2 + 1
  for j in range(j_start, j_end):
    base = S[i:i+j]
    if base in S[i+j:]:
      ans = max(ans, j)


print(ans)

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

ans = 0
for i in range(N):
  j_start = ans + 1
  j_end = (N - i) // 2 + 1
  for j in range(j_start, j_end):
    base = S[i:i+j]
    if base in S[i+j:]:
      ans = max(ans, j)
    else:
      break


print(ans)

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

ans = 0
for i in range(N):
  j_start = ans + 1
  j_end = N - i
  for j in range(j_start, j_end):
    base = S[i:i+j]
    if base in S[i+j:]:
      ans = max(ans, j)


print(ans)

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

ans = 0
for i in range(N):
  j_start = ans + 1
  j_end = (N - i) // 2 + 1
  for j in range(j_start, j_end):
    base = S[i:i+j]
    if base in S[i+j:]:
      ans = max(ans, j)
    else:
      break


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

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

r = np.sum(B)
for i in range(N-1):
  if A[i] + 1 == A[i + 1]:
    r += C[A[i]]

print(r)

Fixed submission:
import numpy as np
 
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
 
r = np.sum(B)
for i in range(N-1):
  if A[i] + 1 == A[i + 1]:
    r += C[A[i]-1]

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

s = input()
t = input()
ls = len(s)
lt = len(t)

if not set(list(t)) <= set(list(s)):
  print(-1)

else:
  d = {}
  for i in range(ls):
    if s[i] in d.keys():
      d[s[i]] += [i+1]
    else:
      d[s[i]] = [i+1]
  
  c = 0
  x = 0
  for j in range(lt):
    a = np.array(d[t[j]])
    idx = min(np.r_[a[a >= x], a[a < x]+ls])
    c += idx - x
    x = c % ls
    
  print(c)

Fixed submission:
import bisect

S = input()
T = input()

ls = len(S)
d = {}
for i, s in enumerate(S):
  if s in d:
    d[s].append(i+1)
  else:
    d[s] = [i+1]


now = 0
ans = 0
pre_t = ''
for t in T:
  if not t in d:
    ans = -1
    break
    
  if t == pre_t:
    idx = bisect.bisect_left(d[t], now+1)
  else:
    idx = bisect.bisect_left(d[t], now)

  if idx == len(d[t]):
    idx = 0
  
  if d[t][idx] > now:
    ans += d[t][idx] - now
  else:
    ans += ls + d[t][idx] - now
  
  now = d[t][idx]
  pre_t = t

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
s = input()
t = input()
ls = len(s)
lt = len(t)

if not set(list(t)) <= set(list(s)):
  print(-1)

else:
  i = 0
  j = 0
  while True:
    if s[i % ls] == t[j]:
      j += 1
    
    if j >= lt:
      break
    
    i += 1

  print(i + 1)



Fixed submission:
import bisect

S = input()
T = input()

ls = len(S)
d = {}
for i, s in enumerate(S):
  if s in d:
    d[s].append(i+1)
  else:
    d[s] = [i+1]


now = 0
ans = 0
pre_t = ''
for t in T:
  if not t in d:
    ans = -1
    break
    
  if t == pre_t:
    idx = bisect.bisect_left(d[t], now+1)
  else:
    idx = bisect.bisect_left(d[t], now)

  if idx == len(d[t]):
    idx = 0
  
  if d[t][idx] > now:
    ans += d[t][idx] - now
  else:
    ans += ls + d[t][idx] - now
  
  now = d[t][idx]
  pre_t = t

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

N = int(input())
S = []
for i in range(N):
  S.append(list(input()))

S = np.array(S)

s = list('abcdefghijklmnopqrstuvwxyz')

T = np.zeros([N, 26])

for i, a in enumerate(s):
  T[:, i] = np.sum(S == a, axis=1)

T3 = np.atleast_3d(T)

print(int((np.sum(np.prod(T3 == T3.T, axis=1)) - N) / 2))



Fixed submission:
def number(x):
  return int((1 + (1 + 8*x)**0.5) / 2)


N = int(input())
d = {}
for i in range(N):
  s = ''.join(sorted(input()))
  if s in d.keys():
    d[s] += number(d[s])
  else:
    d[s] = 0


print(sum(d.values()))

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

N = int(input())
S = []
for i in range(N):
  S.append(list(input()))

S = np.array(S)

s = list('abcdefghijklmnopqrstuvwxyz')

T = np.zeros([N, 26])

for i, a in enumerate(s):
  T[:, i] = np.sum(S == a, axis=1)

T3 = np.atleast_3d(T)
r = np.prod(T3 == T3.T, axis=1)

print((np.sum(r) - len(r)) // 2)

Fixed submission:
def number(x):
  return int((1 + (1 + 8*x)**0.5) / 2)


N = int(input())
d = {}
for i in range(N):
  s = ''.join(sorted(input()))
  if s in d.keys():
    d[s] += number(d[s])
  else:
    d[s] = 0


print(sum(d.values()))

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

N = int(input())
S = []
for i in range(N):
  S.append(list(input()))

S = np.array(S)

s = list('abcdefghijklmnopqrstuvwxyz')

T = np.zeros([N, 26])

for i, a in enumerate(s):
  T[:, i] = np.sum(S == a, axis=1)


c = 0
for i in range(N):
  c += np.sum(np.prod(T[i] == T[i+1:], axis=1))
  
print(c)

Fixed submission:
def number(x):
  return int((1 + (1 + 8*x)**0.5) / 2)


N = int(input())
d = {}
for i in range(N):
  s = ''.join(sorted(input()))
  if s in d.keys():
    d[s] += number(d[s])
  else:
    d[s] = 0


print(sum(d.values()))

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

N = int(input())
S = []
for i in range(N):
  S.append(list(input()))

S = np.array(S)

s = list('abcdefghijklmnopqrstuvwxyz')

T = np.zeros([N, 26])

for i, a in enumerate(s):
  T[:, i] = np.sum(S == a, axis=1)


c = 0
for i in range(N):
  for j in range(i+1, N):
    if (T[i] == T[j]).all():
      c += 1

print(c)

Fixed submission:
def number(x):
  return int((1 + (1 + 8*x)**0.5) / 2)


N = int(input())
d = {}
for i in range(N):
  s = ''.join(sorted(input()))
  if s in d.keys():
    d[s] += number(d[s])
  else:
    d[s] = 0


print(sum(d.values()))
Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())

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

BA.sort(reverse=True)

ans = 0
used = [False] * (M+1)
for b, a in BA:
  if a >= M+1:
    continue
    
  while used[a]:
    a += 1
    if a == M+1:
      break
  
  if a <= M:
    used[a] = True
    ans += b

print(ans)

Fixed submission:
import heapq

N, M = map(int, input().split())
AB = [list(map(int, input().split())) for i in range(N)]
AB.sort()

ans = 0
candidates = []
now = 0
for i in range(M+1):
  for j in range(now, N):
    if AB[j][0] <= i:
      heapq.heappush(candidates, -AB[j][1])
      now = j + 1
      
    else:
      now = j
      break
  
  if candidates:
    ans -= heapq.heappop(candidates)

print(ans)
Buggy python submission (verdict: Runtime Error):
a = int(input())
print(3＊a＊a)


Fixed submission:
a = int(input())
print(3*a*a)
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np

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

B = np.zeros(N)
n = np.arange(1, N+1)
for i in range(N):
  if np.sum(B[n % n[-i-1] == 0]) % 2 != A[-i-1]:
    B[-i-1] = 1

print(int(np.sum(B)))
print(' '.join(map(str, np.where(B == 1)[0]+1)))

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

B = [0] * N
n = [i+1 for i in range(N)]
for i in range(N)[::-1]:
  if sum(B[i::i+1]) % 2 != A[i]:
    B[i] = 1

print(sum(B))
print(*[i+1 for i, b in enumerate(B) if b==1])
Buggy python submission (verdict: Runtime Error):
mod = 10**9 + 7
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]
 
for i in range(2, 10 ** 6 + 1):
    g1.append((g1[-1] * i) % mod)
    inverse.append((-inverse[mod % i] * (mod // i)) % mod)
    g2.append((g2[-1] * inverse[-1]) % mod)
 
 
def comb(n, r, mod):
    if r < 0 or r > n:
        return 0
    r = min(r, n - r)
    return g1[n] * g2[r] * g2[n-r] % mod

N, K = map(int, input().split())
R = N - K

ans = [0]*K
if R == 0:
  ans[0] = 1
elif R == 1:
  ans[0] = 2
  if K >= 2:
    ans[1] = (K-1) % mod
elif R == 2:
  ans[0] = 3
  if K >= 2:
    ans[1] = (3*K - 3) % mod
    if K >= 3:
      ans[2] = (K-1)*(K-2)//2 % mod
else:
  ans[0] = R + 1
  if K >= 2:
    if R > K:
      for i in range(2, K+1):
        ans[i-1] = comb(K-1, i-1)*(comb(R-1, i-2)+2*comb(R-1, i-1)+comb(R-1, i)) % mod
    else:
      for i in range(2, R):
        ans[i-1] = comb(K-1, i-1)*(comb(R-1, i-2)+2*comb(R-1, i-1)+comb(R-1, i)) % mod
      for i in range(R, K+1):
        ans[i-1] = comb(K-1, i-1)*(comb(R-1, i-2)+2*comb(R-1, i-1)) % mod

for a in ans:
  print(a)

Fixed submission:
mod = 10**9 + 7
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

for i in range(2, 10 ** 6 + 1):
    g1.append((g1[-1] * i) % mod)
    inverse.append((-inverse[mod % i] * (mod // i)) % mod)
    g2.append((g2[-1] * inverse[-1]) % mod)


def comb(n, r, mod):
    if r < 0 or r > n:
        return 0
    r = min(r, n - r)
    return g1[n] * g2[r] * g2[n-r] % mod

N, K = map(int, input().split())
R = N - K
for i in range(1, K+1):
  print(comb(K-1, i-1, mod)*comb(R+1, i, mod) % mod)

Buggy python submission (verdict: Runtime Error):
mod = 10**9 + 7
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]
def comb(n, r, mod):
    if r < 0 or r > n:
        return 0
    r = min(r, n - r)
    return g1[n] * g2[r] * g2[n-r] % mod

N, K = map(int, input().split())
R = N - K
for i in range(1, K+1):
  print(comb(K-1, i-1)*comb(R+1, i) % mod)

Fixed submission:
mod = 10**9 + 7
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

for i in range(2, 10 ** 6 + 1):
    g1.append((g1[-1] * i) % mod)
    inverse.append((-inverse[mod % i] * (mod // i)) % mod)
    g2.append((g2[-1] * inverse[-1]) % mod)


def comb(n, r, mod):
    if r < 0 or r > n:
        return 0
    r = min(r, n - r)
    return g1[n] * g2[r] * g2[n-r] % mod

N, K = map(int, input().split())
R = N - K
for i in range(1, K+1):
  print(comb(K-1, i-1, mod)*comb(R+1, i, mod) % mod)
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
MOD = 10**9 + 7

num = []
now = N + 1
i = 1
while True:
  r = N // (i+1) + 1
  if r == now:
    break
  num.append(now - r)
  now = r
  i += 1
  
num += [1] * (N - sum(num))
n = len(num)
dp = [[0]*n for i in range(K)]
for _n in range(n):
  dp[0][_n] = num[_n]

for i in range(1, K):
  s = 0
  for _n in range(n):
    j = n - 1 - _n
    s += dp[i-1][j] % MOD
    s %= MOD
    dp[i][_n] = s * num[_n] % MOD

ans = sum(dp[-1])
print(ans % MOD)

Fixed submission:
N, K = map(int, input().split())
MOD = 10**9 + 7

num = []
now = N + 1
i = 1
while True:
  r = N // (i+1) + 1
  if r == now:
    break
  num.append(now - r)
  now = r
  i += 1
  
num += [1] * (N - sum(num))
n = len(num)
dp = [[0]*n for i in range(K)]
for _n in range(n):
  dp[0][_n] = num[_n]

for i in range(1, K):
  s = 0
  for _n in range(n):
    j = n - 1 - _n
    s += dp[i-1][j] % MOD
    s %= MOD
    dp[i][_n] = s * num[_n] % MOD

ans = sum(dp[-1])
print(ans % MOD)
Buggy python submission (verdict: Runtime Error):
N, X = map(int, input().split())
L = list(map(int, input().split()))

D = [0]
for l in L:
  d = D[-1] + L
  if d <= X:
    D.append(d)
  else:
    break

print(len(D))

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

D = [0]
for l in L:
  d = D[-1] + l
  if d <= X:
    D.append(d)
  else:
    break

print(len(D))
Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
MOD = 10**9 + 7

dp = [[0]*(M+1) for i in range(N+1)]

for i in range(N):
  for j in range(M):
    if S[i] == T[j]:
      dp[i+1][j+1] = (dp[i+1][j] + dp[i][j+1] + 1) % MOD
    else:
      dp[i+1][j+1] = (dp[i+1][j] + dp[i][j+1] - dp[i][j]) % MOD

print((dp[N][M] + 1) % MOD)

Fixed submission:
N, M = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
MOD = 10**9 + 7

dp = [[0]*(M+1) for i in range(N+1)]

for i in range(N):
  for j in range(M):
    if S[i] == T[j]:
      dp[i+1][j+1] = (dp[i+1][j] + dp[i][j+1] + 1) % MOD
    else:
      dp[i+1][j+1] = (dp[i+1][j] + dp[i][j+1] - dp[i][j]) % MOD

print((dp[N][M] + 1) % MOD)
Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())

A = []
for i in range(M):
  A.append(int(input()))

A.sort()
ida = 0
a = A[ida]
mod = 10**9 + 7

x = [1] + [0]*N
if a == 1:
  ida += 1
  if M >= 2:
    a = A[ida]
  else:
    x[1] = 1

for i in range(2, N+1):
  if i == a:
    ida += 1
    if ida >= M:
      a = N+1
    else:
      a = A[ida]
  
    x[i] = 0
  else:
    x[i] = (x[i-1] + x[i-2]) % mod

print(x[N])

Fixed submission:
N, M = map(int, input().split())
x = [1] + [0] * N
broken = [False] * (N+1)
mod = 10**9 + 7

for i in range(M):
  a = int(input())
  broken[a] = True

if not broken[1]:
  x[1] = 1

for i in range(2, N+1):
  if broken[i]:
    continue
  
  x[i] = (x[i-1] + x[i-2]) % mod

print(x[N])
Buggy python submission (verdict: Runtime Error):
MOD = 10**9 + 7
L = input()[::-1]

ans = [1]
for l in L:
  if l == '1':
    if len(ans) == 1:
      ans[0] *= 3
      ans[0] %= MOD
    else:
      ans = [sum(ans) % MOD]
  
  else:
    if len(ans) == 1:
      a = ans[0]
      ans = [a, a, a*3%MOD]
    else:
      a[2] *= 3
      a[2] %= MOD

print(ans[0])

Fixed submission:
MOD = 10**9 + 7
L = input()[1:]

ans = [2, 1]
for l in L:
  ans[1] *= 3
  ans[1] %= MOD
  if l == '1':
    ans[1] += ans[0]
    ans[0] *= 2
    ans[0] %= MOD

print(sum(ans) % MOD)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
import sys
sys.setrecursionlimit(10**9)


N, K = map(int, input().split())
V = deque(list(map(int, input().split())))


def solve(v, k):
  if len(v) == 0 or k <= 0:
    return v, 0
  else:
    v0 = v.popleft()
    v, _a1 = solve(v, k-1)
    _a1 += v0
    v, _a2 = solve(v, k-2)
    v.appendleft(v0)
    v1 = v.pop()
    v, _a3 = solve(v, k-1)
    _a3 += v1
    v, _a4 = solve(v, k-2)
    v.append(v1)
    return v, max(_a1, _a2, _a3, _a4)

print(solve(V, K)[1])

Fixed submission:
import bisect

N, K = map(int, input().split())
V = list(map(int, input().split()))


ans = 0
R = min(N, K)
for r in range(R+1):
  for a in range(r+1):
    left = V[:a]
    b = r - a
    if b == 0:
      right = []
    else:
      right = V[-b:]
    
    v = left + right
    v.sort()
    n_nega = bisect.bisect_left(v, 0)
    k = min(n_nega, K-r)
    ans = max(ans, sum(v[k:]))


print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
import sys
sys.setrecursionlimit(10**9)


N, K = map(int, input().split())
V = deque(list(map(int, input().split())))


def solve(v, k):
  if len(v) == 0 or k <= 0:
    return v, 0
  else:
    v0 = v.popleft()
    v, _a1 = solve(v, k-1)
    _a1 += v0
    v, _a2 = solve(v, k-2)
    v.appendleft(v0)
    v1 = v.pop()
    v, _a3 = solve(v, k-1)
    _a3 += v1
    v, _a4 = solve(v, k-2)
    v.append(v1)
    return v, max(_a1, _a2, _a3, _a4)

print(solve(V, K)[1])

Fixed submission:
import bisect

N, K = map(int, input().split())
V = list(map(int, input().split()))


ans = 0
R = min(N, K)
for r in range(R+1):
  for a in range(r+1):
    left = V[:a]
    b = r - a
    if b == 0:
      right = []
    else:
      right = V[-b:]
    
    v = left + right
    v.sort()
    n_nega = bisect.bisect_left(v, 0)
    k = min(n_nega, K-r)
    ans = max(ans, sum(v[k:]))


print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

H, W = map(int, input().split())
A = [input() for i in range(H)]

Map = [[-1] * W for i in range(H)]

d = deque([])
for i in range(H):
  for j in range(W):
    if A[i][j] == '#':
      Map[i][j] = 0
      d.append([i, j])

ans = 0
while d:
  x, y = d.popleft()
  dist = Map[x][y]
  for dx, dy in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
    u, v = x + dx, y + dy
    if 0<=u<H and 0<=v<W and Map[u][v]==-1:
      Map[u][v] = dist + 1
      ans = max(ans, dist + 1)
      d.append([u, v])

print(ans)

Fixed submission:
from collections import deque

H, W = map(int, input().split())
A = [input() for i in range(H)]

Map = [[-1] * W for i in range(H)]

d = deque([])
for i in range(H):
  for j in range(W):
    if A[i][j] == '#':
      Map[i][j] = 0
      d.append([i, j])

ans = 0
while d:
  x, y = d.popleft()
  dist = Map[x][y]
  for dx, dy in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
    u, v = x + dx, y + dy
    if 0<=u<H and 0<=v<W and Map[u][v]==-1:
      Map[u][v] = dist + 1
      ans = max(ans, dist + 1)
      d.append([u, v])

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


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

ans = 1
a = A.pop()
for i in range(N):
  ans = max(ans, reduce(gcd, A))
  A.appendleft(a)
  a = A.pop()

print(ans)

Fixed submission:
from fractions import gcd

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

L = [0]
R = [0]

g = A[0]
for a in A:
  g = gcd(g, a)
  L.append(g)

A = A[::-1]
g = A[0]
for a in A:
  g = gcd(g, a)
  R.append(g)

R = R[::-1]

ans = 1
for l, r in zip(L, R[1:]):
  ans = max(ans, gcd(l, r))

print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())
S = input()
K = input()
t = S[K-1]
ans = ''
for s in S:
  if s == t:
    ans += s
  else:
    ans += '*'

print(ans)

Fixed submission:
N = int(input())
S = input()
K = int(input())
t = S[K-1]
ans = ''
for s in S:
  if s == t:
    ans += s
  else:
    ans += '*'

print(ans)
Buggy python submission (verdict: Runtime Error):
T, X = map(int, input().split()))
print(T/X)

Fixed submission:
T, X = map(int, input().split())
print(T/X)