Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
n = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

ans = 0
for i in reversed(range(1, n+1)):
    if A[i] <= B[i-1]:
        ans += A[i]
        B[i-1] -= A[i]
        if A[i-1] >= B[i-1]:
            ans += B[i-1]
            A[i-1] -= B[i-1]
        else:
            ans += A[i-1]
            A[i-1] = 0
    else:
        ans += B[i]
        B[i-1] = 0
print(ans)

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

ans = 0

for i in reversed(range(n+1)):
  if i == n:
    temp = min(a[i], b[i-1])
    ans += temp
    b[i-1] -= temp
  elif i == 0:
    ans += min(a[i], b[i])
  else:
    temp1 = min(a[i], b[i])
    ans += temp1
    a[i] -= temp1
    temp2 = min(a[i], b[i-1])
    ans += temp2
    b[i-1] -= temp2
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
#l = [0]*n
l = [int(input()) for i in range(n)]

for i in range(n):
  l_b = l[:i]
  l_a = l[i+1:]
  if i == 0:
    print(max(l_a))
  elif i == n-1:
    print(max(l_b))
  else:
    print(max(max(l_b), max(l_a)))

Fixed submission:
n = int(input())
#l = [0]*n
l = [int(input()) for i in range(n)]

m_l = [0]
m_r = [0]

for i in range(n):
  m_l.append(max(m_l[i], l[i]))
  m_r.append(max(m_r[i], l[-(i+1)]))
m_r = m_r[::-1]
#print(m_l) 
#print(m_r)

for i in range(n):
  print(max(m_l[i], m_r[i+1]))

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
l = [0]*n
for i in range(n):
  l[i] = int(input())

for i in range(n):
  l_b = l[:i]
  l_a = l[i+1:]
  if i == 0:
    print(max(l_a))
  elif i == n-1:
    print(max(l_b))
  else:
    print(max(max(l_b), max(l_a)))


Fixed submission:
n = int(input())
#l = [0]*n
l = [int(input()) for i in range(n)]

m_l = [0]
m_r = [0]

for i in range(n):
  m_l.append(max(m_l[i], l[i]))
  m_r.append(max(m_r[i], l[-(i+1)]))
m_r = m_r[::-1]
#print(m_l) 
#print(m_r)

for i in range(n):
  print(max(m_l[i], m_r[i+1]))
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
A = [int(input()) for _ in range(n)]

B = []
import bisect
for i, a in enumerate(A):
    if len(B) == 0:
        B.append(a)
    else:
        j = bisect.bisect_left(B, a)
        if j == 0:
            B = [a]+B
        elif j == len(B):
            B[-1] = a
        else:
            B[j-1] = a
print(len(B))

Fixed submission:
import bisect
from collections import deque

n = int(input())
l = deque([int(input())])

for i in range(1, n):
  a = int(input())
  p = bisect.bisect_left(l,a)
  if p == 0:
    l.appendleft(a)
  else:
    l[p-1] = a

print(len(l))

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
l = [int(input())]
import bisect
from collections import deque
for i in range(1, n):
  a = int(input())
  p = bisect.bisect_left(l,a)
  if p == 0:
    l = deque(l)
    l.appendleft(a)
    l = list(l)
  else:
    l[p-1] = a

print(len(l))

Fixed submission:
import bisect
from collections import deque

n = int(input())
l = deque([int(input())])

for i in range(1, n):
  a = int(input())
  p = bisect.bisect_left(l,a)
  if p == 0:
    l.appendleft(a)
  else:
    l[p-1] = a

print(len(l))

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
l = [int(input())]
import bisect
from collections import deque
for i in range(1, n):
  a = int(input())
  p = bisect.bisect_left(l,a)
  if p == 0:
    l = deque(l)
    l.appendleft(a)
    l = list(l)
  else:
    l[p-1] = a

print(len(l))

Fixed submission:
import bisect
from collections import deque

n = int(input())
l = deque([int(input())])

for i in range(1, n):
  a = int(input())
  p = bisect.bisect_left(l,a)
  if p == 0:
    l.appendleft(a)
  else:
    l[p-1] = a

print(len(l))

Buggy python submission (verdict: Runtime Error):
n = int(input())
s = str(input())

dp = [[0]*(n+1) for i in range(n+1)]
#dp[n-1][n-1] = 1

for i in reversed(range(n)):
  for j in reversed(range(n)):
    if s[i] == s[j]:
      dp[i][j] = dp[i+1][j+1]+1

#print(dp)

ans = 0
for i in range(n-1):
  for j in range(i, n):
    ans = max(ans, min(dp[i][j], j-i))
    
print(ans)


Fixed submission:
import bisect
from collections import deque

n = int(input())
l = deque([int(input())])

for i in range(1, n):
  a = int(input())
  p = bisect.bisect_left(l,a)
  if p == 0:
    l.appendleft(a)
  else:
    l[p-1] = a

print(len(l))
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.buffer.readline

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

mod = 10**9+7
N = 2*10**2
fac = [1]*(N+1)
finv = [1]*(N+1)
for i in range(N):
    fac[i+1] = fac[i] * (i+1) % mod
finv[-1] = pow(fac[-1], mod-2, mod)
for i in reversed(range(N)):
    finv[i] = finv[i+1] * (i+1) % mod

def prm(n, r, mod):
    if r <0 or r > n:
        return 0
    if r == 0:
        return 1
    return fac[n] * finv[n-r] % mod

s = [0]
visit = [-1]*n
visit[0] = 0
ans = 1
while s:
    v = s.pop()
    if v != 0:
        c = len(g[v])-1
        K = k-2
    else:
        c = len(g[v])+1
        K = k
    ans *= prm(K, c, mod)
    ans %= mod
    for u in g[v]:
        if visit[u] == -1:
            visit[u] = 0
            s.append(u)
print(ans)


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

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

mod = 10**9+7
N = 2*10**5
fac = [1]*(N+1)
finv = [1]*(N+1)
for i in range(N):
    fac[i+1] = fac[i] * (i+1) % mod
finv[-1] = pow(fac[-1], mod-2, mod)
for i in reversed(range(N)):
    finv[i] = finv[i+1] * (i+1) % mod

def prm(n, r, mod):
    if r <0 or r > n:
        return 0
    if r == 0:
        return 1
    return fac[n] * finv[n-r] % mod

s = [0]
visit = [-1]*n
visit[0] = 0
ans = 1
while s:
    v = s.pop()
    if v != 0:
        c = len(g[v])-1
        K = k-2
    else:
        c = len(g[v])+1
        K = k
    ans *= prm(K, c, mod)
    ans %= mod
    for u in g[v]:
        if visit[u] == -1:
            visit[u] = 0
            s.append(u)
print(ans)
Buggy python submission (verdict: Runtime Error):
from collections import deque
n, m = map(int, input().split())

g = [[] for i in range(n)]

for i in range(m):
  u, v = map(int, input().split())
  u, v = u-1, v-1
  g[u].append(v)
# print(g)

s, t = map(int, input().split())
s, t = s-1, t-1

visited = [[-1]*3 for j in range(n)]

l = 0
queue = deque([[s, l]])
visited[s][l] = 0
while queue:
  x, l = queue.popleft()
  if [x, l] == [t, 0]:
    print(visited[x][l]//3)
    exit()
  for x_ in g[x]:
    new_x, new_l = x_, (l+1)%3
    if visited[new_x][new_l] == -1:
      visited[new_x][new_l] = visited[x][l]+1
      queue.append([new_x, new_l])
    
print(visited[t][0])

Fixed submission:
n = int(input())
ds = list(map(int, input().split()))
ds.sort()
#print(ds)

abc = ds[:n//2]
arc = ds[n//2:]
#print(abc)
#print(arc)

print(min(arc)-max(abc))
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()))

M = 10**9+7

dp = [[1]*(m+1) for _ 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]
    else:
      dp[i+1][j+1] = dp[i+1][j] + dp[i][j+1] - dp[i][j]
    dp[i+1][j+1] %= M

#print(dp)
print(dp[-1][-1]%M)

Fixed submission:
n, m = map(int, input().split())
s = list(map(int, input().split()))
t = list(map(int, input().split()))

M = 10**9+7

dp = [[1]*(m+1) for _ 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]
    else:
      dp[i+1][j+1] = dp[i+1][j] + dp[i][j+1] - dp[i][j]
    dp[i+1][j+1] %= M

#print(dp)
print(dp[-1][-1]%M)
Buggy python submission (verdict: Runtime Error):
n = int(input())
XY = []
for i in range(n):
    x, y = map(int, input().split())
    XY.append((x, y))

D = {}
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        a = XY[i][0]
        b = XY[i][1]
        c = XY[j][0]
        d = XY[j][1]
        p = c-a
        q = d-b
        if (p, q) in D:
            D[(p, q)] += 1
        else:
            D[(p,q)] = 1

D = list(D.items())
D.sort(key = lambda x: -x[1])
print(n-D[0][1])


Fixed submission:
n = int(input())
XY = []
for i in range(n):
    x, y = map(int, input().split())
    XY.append((x, y))

if n == 1:
    print(1)
    exit()
    
D = {}
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        a = XY[i][0]
        b = XY[i][1]
        c = XY[j][0]
        d = XY[j][1]
        p = c-a
        q = d-b
        if (p, q) in D:
            D[(p, q)] += 1
        else:
            D[(p,q)] = 1

D = list(D.items())
D.sort(key = lambda x: -x[1])
print(n-D[0][1])
Buggy python submission (verdict: Time Limit Exceeded):
h, w = map(int, input().split())

ss = [[] for i in range(h)]

for i in range(h):
  ss[i] = list(str(input()))

s_h_l = [[0]*w for i in range(h)]
for i in range(h):
  light = 0
  for j in range(w):
    s_h_l[i][j] = light
    if ss[i][j] == '.':
      light += 1
    else:
      light = 0
      s_h_l[i][j] = 0
      
s_h_r = [[0]*w for i in range(h)]
for i in range(h):
  light = 0
  for j in reversed(range(w)):
    s_h_r[i][j] = light
    if ss[i][j] == '.':
      light += 1
    else:
      light = 0
      s_h_r[i][j] = 0

s_w_u = [[0]*w for i in range(h)]
for i in range(w):
  light = 0
  for j in range(h):
    s_w_u[j][i] = light
    if ss[j][i] == '.':
      light += 1
    else:
      light = 0
      s_w_u[j][i] = 0
      
s_w_d = [[0]*w for i in range(h)]
for i in range(w):
  light = 0
  for j in reversed(range(h)):
    s_w_d[j][i] = light
    if ss[j][i] == '.':
      light += 1
    else:
      light = 0
      s_w_d[j][i] = 0   

ans = 0
for i in range(h):
  for j in range(w):
    ans = max(ans, s_h_r[i][j]+s_h_l[i][j]+s_w_u[i][j]+s_w_d[i][j]+1)
print(ans)

Fixed submission:
h, w = map(int, input().split())

ss = [[] for i in range(h)]

for i in range(h):
  ss[i] = list(str(input()))

s_h_l = [[0]*w for i in range(h)]
for i in range(h):
  light = 0
  for j in range(w):
    s_h_l[i][j] = light
    if ss[i][j] == '.':
      light += 1
    else:
      light = 0
      s_h_l[i][j] = 0
      
s_h_r = [[0]*w for i in range(h)]
for i in range(h):
  light = 0
  for j in reversed(range(w)):
    s_h_r[i][j] = light
    if ss[i][j] == '.':
      light += 1
    else:
      light = 0
      s_h_r[i][j] = 0

s_w_u = [[0]*w for i in range(h)]
for i in range(w):
  light = 0
  for j in range(h):
    s_w_u[j][i] = light
    if ss[j][i] == '.':
      light += 1
    else:
      light = 0
      s_w_u[j][i] = 0
      
s_w_d = [[0]*w for i in range(h)]
for i in range(w):
  light = 0
  for j in reversed(range(h)):
    s_w_d[j][i] = light
    if ss[j][i] == '.':
      light += 1
    else:
      light = 0
      s_w_d[j][i] = 0   

ans = 0
for i in range(h):
  for j in range(w):
    ans = max(ans, s_h_r[i][j]+s_h_l[i][j]+s_w_u[i][j]+s_w_d[i][j]+1)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
s = str(input())

ans = 0
while True:
    t = s.count('ABC')
    if t == 0:
        break
    ans += t
    s = s.replace('ABC', 'BCA')
print(ans)

Fixed submission:
s = str(input())
s = s.replace('BC', 'D')
n = len(s)

ans = 0
cnt = 0
for i in range(n):
    if s[i] == 'A':
        cnt += 1
    if s[i] == 'D':
        ans += cnt
    if s[i] == 'B' or s[i] == 'C':
        cnt = 0
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
s = str(input())

ans = 0
while True:
    t = s.count('ABC')
    if t == 0:
        break
    ans += t
    s = s.replace('ABC', 'BCA')
print(ans)

Fixed submission:
s = str(input())
s = s.replace('BC', 'D')
n = len(s)

ans = 0
cnt = 0
for i in range(n):
    if s[i] == 'A':
        cnt += 1
    if s[i] == 'D':
        ans += cnt
    if s[i] == 'B' or s[i] == 'C':
        cnt = 0
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int, input().split())
s = set(range(1, n+1))
for i in range(m):
    l, r = map(int, input().split())
    s = s & set(range(l, r+1))
print(len(s))


Fixed submission:
n, m = map(int, input().split())
ls = [0]*m
rs = [0]*m

for i in range(m):
  l, r  = map(int, input().split())
  ls[i] = l
  rs[i] = r

print(max(min(rs)-max(ls)+1,0))

Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int, input().split())
x = range(1, n+1)

for i in range(m):
  l, r  = map(int, input().split())
  y = range(l, r+1)
  x = list(set(x) & set(y))

print(len(x))

Fixed submission:
n, m = map(int, input().split())
ls = [0]*m
rs = [0]*m

for i in range(m):
  l, r  = map(int, input().split())
  ls[i] = l
  rs[i] = r

print(max(min(rs)-max(ls)+1,0))
Buggy python submission (verdict: Runtime Error):
n, k = map(int, input().split())

import math
ans = 0
for i in range(1, n+1):
    if i >= k:
        t = 0
    else:
        t = math.ceil(math.log2(k/i))
    #print(t)
    ans += (1/n)*((1/2)**t)
print(ans)


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

ans = 0
for i in range(1, n+1):
  x = max(math.ceil(math.log2(k)-math.log2(i)), 0)
  # print(x)
  ans += (1/n) * ((1/2)**x)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
r, g, b, n = map(int, input().split())

ans = 0
for i in range(n//r+1):
  for j in range(n//g+1):
    k = n - r*i -g*j
    if k >= 0 and k%b == 0:
      #print(i, j, k)
      ans += 1
      
print(ans)

Fixed submission:
r, g, b, n = map(int, input().split())

ans = 0
for i in range(n//r+1):
  for j in range(n//g+1):
    k = n - r*i -g*j
    if k >= 0 and k%b == 0:
      #print(i, j, k)
      ans += 1
      
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
x, y, z, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

l = []
for i in range(len(a)):
  for j in range(len(b)):
    l.append(a[i]+b[j])

l.sort(reverse=True)
if k <= len(l):
  l = l[:k]

m = []
for i in range(len(l)):
  for j in range(len(c)):
    m.append(l[i]+c[j])

m.sort(reverse=True)   
for i in range(k):
  print(m[i])



Fixed submission:
x, y, z, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

l = []
for i in range(len(a)):
  for j in range(len(b)):
    l.append(a[i]+b[j])

l.sort(reverse=True)
if k <= len(l):
  l = l[:k]

m = []
for i in range(len(l)):
  for j in range(len(c)):
    m.append(l[i]+c[j])

m.sort(reverse=True)   
for i in range(k):
  print(m[i])
Buggy python submission (verdict: Time Limit Exceeded):
n, q = map(int, input().split())
s = str(input())

cum = [0]*n

for i in range(1, len(s)+1):
  sp = s[:i]
  cum[i-1] = sp.count('AC')

for i in range(q):
  l, r = map(int, input().split())
  print(cum[r-1]-cum[l-1])

Fixed submission:
n, q = map(int, input().split())
s = str(input())

cum = [0]*n
current = 0

flag = 0

for i in range(1, len(s)):
  if s[i-1] == 'A' and s[i] =='C':
    current += 1
  cum[i] = current

for i in range(q):
  l, r = map(int, input().split())
  print(cum[r-1]-cum[l-1])

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

cum = [0]*n

for i in range(1, len(s)+1):
  sp = s[:i]
  cum[i-1] = sp.count('AC')

for i in range(q):
  l, r = map(int, input().split())
  print(cum[r-1]-cum[l-1])

Fixed submission:
n, q = map(int, input().split())
s = str(input())

cum = [0]*n
current = 0

flag = 0

for i in range(1, len(s)):
  if s[i-1] == 'A' and s[i] =='C':
    current += 1
  cum[i] = current

for i in range(q):
  l, r = map(int, input().split())
  print(cum[r-1]-cum[l-1])

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

for i in range(q):
  l, r = map(int, input().split()) 
  sp = s[l-1:r]
  print(sp.count('AC'))


Fixed submission:
n, q = map(int, input().split())
s = str(input())

cum = [0]*n
current = 0

flag = 0

for i in range(1, len(s)):
  if s[i-1] == 'A' and s[i] =='C':
    current += 1
  cum[i] = current

for i in range(q):
  l, r = map(int, input().split())
  print(cum[r-1]-cum[l-1])

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

for i in range(q):
  l, r = map(int, input().split()) 
  sp = s[l-1:r]
  print(sp.count('AC'))


    

Fixed submission:
n, q = map(int, input().split())
s = str(input())

cum = [0]*n
current = 0

flag = 0

for i in range(1, len(s)):
  if s[i-1] == 'A' and s[i] =='C':
    current += 1
  cum[i] = current

for i in range(q):
  l, r = map(int, input().split())
  print(cum[r-1]-cum[l-1])
Buggy python submission (verdict: Time Limit Exceeded):
s = str(input())
n = len(s)
 
while '01' in s or '10' in s:
  s = s.replace('01', '').replace('10', '')
print(n-len(s))

Fixed submission:
s = str(input())
print(2*(min(s.count('0'), s.count('1'))))

Buggy python submission (verdict: Time Limit Exceeded):
s = str(input())
n = len(s)

while '01' in s or '10' in s:
  s = s.replace('01', '')
  s = s.replace('10', '')

print(n-len(s))

Fixed submission:
s = str(input())
print(2*(min(s.count('0'), s.count('1'))))
Buggy python submission (verdict: Time Limit Exceeded):
a, b, q = map(int, input().split())
S = [int(input()) for _ in range(a)]
T = [int(input()) for _ in range(b)]
S.sort()
T.sort()
S = [-float('inf')] + S + [float('inf')]
T = [-float('inf')] + T + [float('inf')]

import bisect
for _ in range(q):
    x = int(input())
    i = bisect.bisect_right(S, x)
    j = bisect.bisect_right(T, x)
    ans = float('inf')
    for s in [S[i-1], S[i]]:
        for t in [T[j-1], T[j]]:
            d1 = abs(s-x) + abs(t-s)
            d2 = abs(t-x) + abs(s-t)
            ans = min([ans, d1, d2])
    print(ans)

Fixed submission:
a, b, q = map(int, input().split())
S = [int(input()) for _ in range(a)]
T = [int(input()) for _ in range(b)]
S.sort()
T.sort()
INF = 10**18
S = [-INF] + S + [INF]
T = [-INF] + T + [INF]

import bisect
for _ in range(q):
    x = int(input())
    i = bisect.bisect_right(S, x)
    j = bisect.bisect_right(T, x)
    ans = INF
    for s in [S[i-1], S[i]]:
        for t in [T[j-1], T[j]]:
            d1 = abs(s-x) + abs(t-s)
            d2 = abs(t-x) + abs(s-t)
            ans = min([ans, d1, d2])
    print(ans)
Buggy python submission (verdict: Runtime Error):
k, a, b = map(int, input().split())
if b-a <= 1:
    ans = k+1
else:
    if k-1 >= a:
        r = k-a+1
        if r%2 == 0:
            ans = a+(b-a)*(r//2)
        else:
            ans = a+(b-a)*((r-1)//2)+1
print(ans)

Fixed submission:
k, a, b = map(int, input().split())
if b-a <= 1:
    ans = k+1
else:
    if k-1 >= a:
        r = k-a+1
        if r%2 == 0:
            ans = a+(b-a)*(r//2)
        else:
            ans = a+(b-a)*((r-1)//2)+1
    else:
        ans = k+1
print(ans)
Buggy python submission (verdict: Runtime Error):
n, m = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

mod = 10**9+7

A_ = set(A)
B_ = set(B)

if len(A) != len(A_) or len(B) != len(B_):
    print(0)
    exit()

A.sort()
B.sort()

import bisect

ans = 1
for i in reversed(range(1, n*m+1)):
    if i in A_ and i in B_:
        ans *= 1
    elif i in A_ and i not in B_:
        ans *= (len(B)-bisect.bisect_left(B, i))
    elif i not in A_ and i in B_:
        ans *= (len(A)-bisect.bisect_left(A, i))
    else:
        b = len(B)-bisect.bisect_left(B, i)
        ans *= a*b-(len(A)*len(B)-i)
    ans %= mod
print(ans)

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

mod = 10**9+7

A_ = set(A)
B_ = set(B)

if len(A) != len(A_) or len(B) != len(B_):
    print(0)
    exit()

A.sort()
B.sort()

import bisect

ans = 1
for i in reversed(range(1, n*m+1)):
    if i in A_ and i in B_:
        ans *= 1
    elif i in A_ and i not in B_:
        ans *= (len(B)-bisect.bisect_left(B, i))
    elif i not in A_ and i in B_:
        ans *= (len(A)-bisect.bisect_left(A, i))
    else:
        a = len(A)-bisect.bisect_left(A, i)
        b = len(B)-bisect.bisect_left(B, i)
        ans *= a*b-(len(A)*len(B)-i)
    ans %= mod
    
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
hs = list(map(int, input().split()))

hs += [0]*k

dp = [float('inf')]*(n+k)

dp[0] = 0

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


Fixed submission:
n, k = map(int, input().split())
hs = list(map(int, input().split()))
 
dp = [0]*n
 
for i in range(1, n):
  first = max(0, i-k)
  dp[i] = min([d + abs(hs[i]-h) for d, h in zip(dp[first:i], hs[first:i])])
print(dp[-1])

Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
h = list(map(int, input().split()))
 
a = [0]*n
 
for i in range(1, n):
  a[i] = min([a[j] + abs(h[i]-h[j]) for j in range(max(0, i-k), i)])
print(a[-1])

Fixed submission:
n, k = map(int, input().split())
hs = list(map(int, input().split()))
 
dp = [0]*n
 
for i in range(1, n):
  first = max(0, i-k)
  dp[i] = min([d + abs(hs[i]-h) for d, h in zip(dp[first:i], hs[first:i])])
print(dp[-1])

Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
h = list(map(int, input().split()))
 
a = [0]*n
 
for i in range(1, n):
  b = [a[j] + abs(h[i]-h[j]) for j in range(max(0, i-k), i)]
  a[i] = min(b)
print(a[-1])


Fixed submission:
n, k = map(int, input().split())
hs = list(map(int, input().split()))
 
dp = [0]*n
 
for i in range(1, n):
  first = max(0, i-k)
  dp[i] = min([d + abs(hs[i]-h) for d, h in zip(dp[first:i], hs[first:i])])
print(dp[-1])

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

a = [0]*n

for i in range(1, n):
  b = a[max(0, i-k)] + abs(h[i]-h[max(0, i-k)])
  for j in range(max(0, i-k), i):
    b = min(b, a[j] + abs(h[i]-h[j]))
  a[i] = b
print(a[-1])

Fixed submission:
n, k = map(int, input().split())
hs = list(map(int, input().split()))
 
dp = [0]*n
 
for i in range(1, n):
  first = max(0, i-k)
  dp[i] = min([d + abs(hs[i]-h) for d, h in zip(dp[first:i], hs[first:i])])
print(dp[-1])
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np

N, W = map(int, input().split())
ws = [0]*N
vs = [0]*N
for i in range(N):
  w, v = map(int, input().split()) 
  ws[i] = w
  vs[i] = v

dp = np.zeros((N+1, W+1), dtype='uint64')
  
for i in range(1, N+1):
  for sum_w in range(W+1):
    if sum_w - ws[i-1] >= 0:
    	dp[i][sum_w] = max(dp[i-1][sum_w], dp[i-1][sum_w-ws[i-1]]+vs[i-1])
    dp[i][sum_w] = max(dp[i][sum_w], dp[i-1][sum_w])

print(max(dp[N, :]))
  

Fixed submission:
import numpy as np

N, W = map(int, input().split())

dp = np.zeros((N+1, W+1), dtype='uint64')

for i in range(N):
  w, v = map(int, input().split()) 
  dp[i+1][:w] = dp[i][:w]
  dp[i+1][w:] = np.maximum(dp[i][w:], dp[i][:-w]+v)
print(np.max(dp[N]))

Buggy python submission (verdict: Time Limit Exceeded):
N, W = map(int, input().split())
ws = [0]*N
vs = [0]*N
for i in range(N):
  w, v = map(int, input().split()) 
  ws[i] = w
  vs[i] = v

dp = [[0]*(W+1) for i in range(N+1)]
for i in range(1, N+1):
  for sum_w in range(W+1):
    if sum_w - ws[i-1] >= 0:
    	dp[i][sum_w] = max(dp[i][sum_w], dp[i-1][sum_w-ws[i-1]]+vs[i-1])
    dp[i][sum_w] = max(dp[i][sum_w], dp[i-1][sum_w])

print(max(dp[-1]))
  

Fixed submission:
import numpy as np

N, W = map(int, input().split())

dp = np.zeros((N+1, W+1), dtype='uint64')

for i in range(N):
  w, v = map(int, input().split()) 
  dp[i+1][:w] = dp[i][:w]
  dp[i+1][w:] = np.maximum(dp[i][w:], dp[i][:-w]+v)
print(np.max(dp[N]))