Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import queue
h,w = map(int,input().split())
grid = [list(input()) for _ in range(h)]
nxt = queue.Queue()
for i in range(h):
		for j in range(w):
			if grid[i][j] == "#":
				nxt.put((i,j,0))
a=0
while not nxt.empty():
	i,j,t = nxt.get()
	if t > a:
		a+=1
	for i,j in ((i-1,j),(i+1,j),(i,j-1),(i,j+1)):
		if (-1<i<h)&(-1<j<w):
			if grid[i][j] == ".":
				grid[i][j] = "#"
				nxt.put((i,j,t+1))
print(a)

Fixed submission:
from collections import deque
h,w = map(int,input().split())
grid = [list(input()) for _ in range(h)]
nxt = deque()
for i in range(h):
		for j in range(w):
			if grid[i][j] == "#":
				nxt.append((i,j,0))
a=0
while nxt:
	i,j,t = nxt.popleft()
	if t > a:
		a+=1
	for i,j in ((i-1,j),(i+1,j),(i,j-1),(i,j+1)):
		if (-1<i<h)&(-1<j<w) and grid[i][j] == ".":
				grid[i][j] = "#"
				nxt.append((i,j,t+1))
print(a)

Buggy python submission (verdict: Time Limit Exceeded):
import queue
h,w = map(int,input().split())
grid = [list(input()) for _ in range(h)]
nxt = queue.Queue()
for i in range(h):
		for j in range(w):
			if grid[i][j] == "#":
				nxt.put((i,j,0))
a=0
while not nxt.empty():
	i,j,t = nxt.get()
	if t > a:
		a+=1
	for i,j in ((i-1,j),(i+1,j),(i,j-1),(i,j+1)):
		if (-1<i<h)&(-1<j<w):
			if grid[i][j] == ".":
				grid[i][j] = "#"
				nxt.put((i,j,t+1))
print(a)

Fixed submission:
from collections import deque
h,w = map(int,input().split())
grid = [list(input()) for _ in range(h)]
nxt = deque()
for i in range(h):
		for j in range(w):
			if grid[i][j] == "#":
				nxt.append((i,j,0))
a=0
while nxt:
	i,j,t = nxt.popleft()
	if t > a:
		a+=1
	for i,j in ((i-1,j),(i+1,j),(i,j-1),(i,j+1)):
		if (-1<i<h)&(-1<j<w) and grid[i][j] == ".":
				grid[i][j] = "#"
				nxt.append((i,j,t+1))
print(a)
Buggy python submission (verdict: Runtime Error):
a,b,t = input().split()
print((t//a)*b)

Fixed submission:
a,b,t = map(int,input().split())
print((t//a)*b)
Buggy python submission (verdict: Time Limit Exceeded):
import functools,fractions
def lgcd(list):
  return functools.reduce(fractions.gcd, list)

n = int(input())
nums = list(map(int,input().split()))
cand = []
cand.append(lgcd(nums[1:]))
cand.append(lgcd(nums[:-1]))
for i in range(n-2):
  i += 1
  cand.append(lgcd(nums[:i]+nums[i+1:]))
print(max(cand))

Fixed submission:
from collections import deque
from fractions import gcd
n=int(input())
a=list(map(int,input().split()));g=a[-1]
b=deque([a[0]])
for num in reversed(a[1:]):
	g=gcd(g,num)
	b.appendleft(g)
m=b[0];gg=a[0]
for i,j in enumerate(a[:n-1]):
	gg=gcd(gg,j)
	m=max(m,gcd(gg,b[i+1]))
print(m)

Buggy python submission (verdict: Time Limit Exceeded):
import functools,fractions
def lgcd(list):
  return functools.reduce(fractions.gcd, list)

n = int(input())
nums = list(map(int,input().split()))
cand = []
cand.append(lgcd(nums[1:]))
cand.append(lgcd(nums[:-1]))
for i in range(n-2):
  i += 1
  cand.append(lgcd(nums[:i]+nums[i+1:]))
print(max(cand))

Fixed submission:
from collections import deque
from fractions import gcd
n=int(input())
a=list(map(int,input().split()));g=a[-1]
b=deque([a[0]])
for num in reversed(a[1:]):
	g=gcd(g,num)
	b.appendleft(g)
m=b[0];gg=a[0]
for i,j in enumerate(a[:n-1]):
	gg=gcd(gg,j)
	m=max(m,gcd(gg,b[i+1]))
print(m)
Buggy python submission (verdict: Runtime Error):
input()
s=input()
k=int(input()
for c in s:
 if c!=s[k-1]:
  print("*",end="")
 else:
  print(c,end="")
print("")

Fixed submission:
input()
s=input()
k=int(input())
for c in s:
	if c!=s[k-1]:
		print("*",end="")
	else:
		print(c,end="")
print("")
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import*
n,k=map(int,input().split())
s=input()
t=[0]*(s[0]=="0")+[len(list(g)) for _,g in groupby(s)]+[0]*(s[-1]=="0"or(1-("1"in s)))
a,b=t[::2],t[1::2]
l=len(t)//2;k=min(k,l)
print(max(sum(a[i:i+k+1]+b[i:i+k])for i in range(l+1-k)))

Fixed submission:
from itertools import*
n,k=map(int,input().split())
s=input()
t=[0]*(s[0]=="0")+[len(list(g)) for _,g in groupby(s)]+[0]*(s[-1]=="0"or(1-("1"in s)))
a,b=t[::2],t[1::2]
l=len(t)//2;k=min(k,l)
t=r=sum(a[:k+1]+b[:k]) 
for w,x,y,z in zip(a,b,a[k+1:],b[k:]):
	t+=-w-x+y+z
	r=max(r,t)
print(r)
Buggy python submission (verdict: Runtime Error):
m=map;l=lambda;*a=m(int,open(0));b=m(l x:-x%10,a);c=m(l x:--x//10,a);print(sum(c)+min(b))

Fixed submission:
*a,=map(int,open(0));print(-max(-j%10for j in a)-sum(-i//10for i in a)*10)
Buggy python submission (verdict: Time Limit Exceeded):
x,y,z,k,*L=map(int,open(0).read().split())
a=L[:x];b=L[x:x+y];c=sorted(L[x+y:])[::-1]
ab=sorted(i+j for i in a for j in b)[::-1][:min(x*y,k)]
print(*sorted(i+j for i in ab for j in c)[::-1][:k],sep="\n")

Fixed submission:
x,y,z,k,*L=map(int,open(0).read().split())
a=L[:x];b=L[x:x+y];c=sorted(L[x+y:])[::-1]
ab=sorted(i+j for i in a for j in b)[::-1][:min(x*y,k)]
print(*sorted(i+j for i in ab for j in c)[::-1][:k],sep="\n")
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
n,q=map(int,input().split())
s=input()
Q=[input().rsplit() for _ in range(q)]
l,r=-1,n
while r-l>1:
	c=m=(l+r)//2
	for t,d in Q:
		if s[c]==t:
			c+= 1 if d=="R" else -1
			if c==-1 or c==n:
				break
	if c==-1:l=m
	else:r=m
a=l
l,r=-1,n
while r-l>1:
	c=m=(l+r)//2
	for t,d in Q:
		if s[c]==t:
			c+= 1 if d=="R" else -1
			if c==-1 or c==n:
				break
	if c==n:r=m
	else:l=m
b=r
print(0 if b<=a else b-a-1)

Fixed submission:
import sys
input = sys.stdin.readline
n,q=map(int,input().split())
s=input()
Q=[input().rsplit() for _ in range(q)]
l,r=-1,n
while r-l>1:
	c=m=(l+r)//2
	for t,d in Q:
		if s[c]==t:
			c+= 1 if d=="R" else -1
			if c==-1 or c==n:
				break
	if c==-1:l=m
	else:r=m
a=l
l,r=-1,n
while r-l>1:
	c=m=(l+r)//2
	for t,d in Q:
		if s[c]==t:
			c+= 1 if d=="R" else -1
			if c==-1 or c==n:
				break
	if c==n:r=m
	else:l=m
b=r
print(0 if b<=a else b-a-1)
Buggy python submission (verdict: Time Limit Exceeded):
n,q=map(int,input().split())
s=input()
for i in range(q):
  a,b=map(int,input().split())
  if b==n:b=-1
  print(s[a-1:b].count("AC"))

Fixed submission:
from bisect import bisect_left
n,q=map(int,input().split())
s=input().replace("AC","XY")
ref=[i for i,j in enumerate(s) if j=="X"]
for _ in range(q):
	a,b=map(int,input().split())
	a-=1;b-=1
	print(bisect_left(ref,b)-bisect_left(ref,a))
Buggy python submission (verdict: Runtime Error):
I=lambda:map(int,input().split())
n,m,c=I()
b=list(I())
A=[];c=0
A+=list(I())
for a in A:
  d=0
  for i,j in zip(b,a):
    d+=i*j
  c+=(c+d>0)
print(c)

Fixed submission:
I=lambda:map(int,input().split())
n,m,c=I()
b=list(I())
A=[list(I()) for _ in[0]*n]
e=0
for a in A:
  d=0
  for i,j in zip(b,a):
    d+=i*j
  e+=(d+c>0)
print(e)
Buggy python submission (verdict: Time Limit Exceeded):
F=lambda x:x if P[x]<0else F(P[x]);N,M,*X=map(int,open(0).read().split());P=[-1]*-~N;S=N*~-N//2;r=[];exec("r+=S,;b,a=sorted(map(F,(X.pop(),X.pop())))\nif a!=b:S-=P[a]*P[b];P[a]+=P[b];P[b]=a\n"*M);print(*r[::-1])

Fixed submission:
class UnionFind():
	def __init__(self, n):
		self.n = n
		self.root = [-1]*(n+1)
		self.rank = [0]*(n+1)

	def find(self, x):
		if self.root[x] < 0:
			return x
		else:
			self.root[x] = self.find(self.root[x])
			return self.root[x]
			
	def unite(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return 0
		elif self.rank[x] > self.rank[y]:
			self.root[x] += self.root[y]
			self.root[y] = x
		else:
			self.root[y] += self.root[x]
			self.root[x] = y
			if self.rank[x] == self.rank[y]:
				self.rank[y] += 1

	def isSame(self, x, y):
		return self.find(x) == self.find(y)

	def size(self, x):
		return -self.root[self.find(x)]
		
n,m,*L=map(int,open(0).read().split())
L=L[:1:-1]
ans=[n*(n-1)//2]
uf=UnionFind(n)
for a,b in zip(*[iter(L)]*2):
	if not uf.isSame(a,b):
		ans.append(ans[-1]-uf.size(a)*uf.size(b))
		uf.unite(a,b)
	else:
		ans.append(ans[-1])
print(*ans[::-1])
Buggy python submission (verdict: Runtime Error):
a=map(int,input().split())
print(a[0]*a[1]//2)

Fixed submission:
a=list(map(int,input().split()))
print(a[0]*a[1]//2)
Buggy python submission (verdict: Runtime Error):
N,W=map(int,input().split())
dp=[[0]*(W+1) for _ in range(N+1)]
for i in range(1,N+1):
	w,v=map(int,input().split())
	for j in range(1,W+1):
		if j-w>=0:
			dp[i][j]=max(dp[i-1][j],dp[i-1][j-w]+v)
		else:
			dp[i][j]=dp[i-1][j]
print(dp[N][W])

Fixed submission:
n,*h=map(int,open(0).read().split())
dp=[0]*n
dp[0]=0
dp[1]=abs(h[0]-h[1])
for i in range(2,n):
	dp[i]=min(dp[i-2]+abs(h[i-2]-h[i]),dp[i-1]+abs(h[i-1]-h[i]))
print(dp[n-1])

Buggy python submission (verdict: Runtime Error):
n,k,*h=map(int,open(0).read().split())
INF=float("inf")
dp=[INF]*n
dp[0]=0
dp[1]=abs(h[0]-h[1])
for i in range(2,n):
	width = k
	if i<k:
		width=i
	for j in range(1,width+1):
		dp[i] = min( dp[i] , dp[i-k]+abs(h[i-j]-h[i]) )
print(dp[-1])

Fixed submission:
n,*h=map(int,open(0).read().split())
dp=[0]*n
dp[0]=0
dp[1]=abs(h[0]-h[1])
for i in range(2,n):
	dp[i]=min(dp[i-2]+abs(h[i-2]-h[i]),dp[i-1]+abs(h[i-1]-h[i]))
print(dp[n-1])
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
n,k,*h=map(int,open(0).read().split())
h=deque(h)
INF=float("inf")
dp=deque([0,abs(h[0]-h[1])])
for i in range(2,n):
	width = k
	tmp=INF
	if i<k:
		width=i
	for j in range(1,width+1):
		tmp = min( tmp , dp[i-j]+abs(h[i-j]-h[i]) )
	dp.append(tmp)
print(dp[-1])

Fixed submission:
n,k,*h=map(int,open(0).read().split())
INF=float("inf")
dp=[INF]*n
dp[0]=0
dp[1]=abs(h[0]-h[1])
for i in range(2,n):
	width = k
	if i<k:
		width=i
	for j in range(1,width+1):
		dp[i] = min( dp[i] , dp[i-j]+abs(h[i-j]-h[i]) )
print(dp[-1])

Buggy python submission (verdict: Runtime Error):
from collections import deque
n,k,*h=map(int,open(0).read().split())
h=deque(h)
INF=float("inf")
dp=deque([0,abs(h[0]-h[1])])
for i in range(2,n):
	width = k
	tmp=INF
	if i<k:
		width=i
	for j in range(1,width+1):
		tmp = min( tmp , dp[i-k]+abs(h[i-j]-h[i]) )
	dp.append(tmp)
print(dp[-1])

Fixed submission:
n,k,*h=map(int,open(0).read().split())
INF=float("inf")
dp=[INF]*n
dp[0]=0
dp[1]=abs(h[0]-h[1])
for i in range(2,n):
	width = k
	if i<k:
		width=i
	for j in range(1,width+1):
		dp[i] = min( dp[i] , dp[i-j]+abs(h[i-j]-h[i]) )
print(dp[-1])

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
n,k,*h=map(int,open(0).read().split())
h=deque(h)
INF=float("inf")
dp=deque([0,abs(h[0]-h[1])])
for i in range(2,n):
	width = k
	tmp=INF
	if i<k:
		width=i
	for j in range(1,width+1):
		tmp = min( tmp , dp[i-j]+abs(h[i-j]-h[i]) )
	dp.append(tmp)
print(dp[-1])

Fixed submission:
n,k,*h=map(int,open(0).read().split())
INF=float("inf")
dp=[INF]*n
dp[0]=0
dp[1]=abs(h[0]-h[1])
for i in range(2,n):
	width = k
	if i<k:
		width=i
	for j in range(1,width+1):
		dp[i] = min( dp[i] , dp[i-j]+abs(h[i-j]-h[i]) )
print(dp[-1])
Buggy python submission (verdict: Time Limit Exceeded):
N,W=map(int,input().split())
dp=[[0]*(W+1) for _ in range(N+1)]
for i in range(1,N+1):
	w,v=map(int,input().split())
	for j in range(1,W+1):
		if j-w>=0:
			dp[i][j]=max(dp[i-1][j],dp[i-1][j-w]+v)
		else:
			dp[i][j]=dp[i-1][j]
print(dp[N][W])

Fixed submission:
N,W=map(int,input().split())
dp=[[0]*(W+1) for _ in range(N+1)]
for i in range(1,N+1):
	w,v=map(int,input().split())
	for j in range(1,W+1):
		if j-w>=0:
			dp[i][j]=max(dp[i-1][j],dp[i-1][j-w]+v)
		else:
			dp[i][j]=dp[i-1][j]
print(dp[N][W])
Buggy python submission (verdict: Time Limit Exceeded):
s=input();t=input()
ls=len(s);lt=len(t)
dp=[[0]*(lt+1) for _ in range(ls+1)]
for i in range(ls):
  for j in range(lt):
    if s[i]==t[j]:
      dp[i+1][j+1]=dp[i][j]+1
    else:
      dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1])
ans=""
while ls and lt:
  if dp[ls][lt]==dp[ls-1][lt]:
    ls-=1
  elif dp[ls][lt]==dp[ls][lt-1]:
    lt-=1
  else:
    ls-=1;lt-=1
    ans+=s[ls]
print(ans[::-1])

Fixed submission:
s=input();t=input()
ls=len(s);lt=len(t)
dp=[[0]*(lt+1) for _ in range(ls+1)]
for i in range(ls):
  for j in range(lt):
    if s[i]==t[j]:
      dp[i+1][j+1]=dp[i][j]+1
    else:
      dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1])
ans=""
while ls and lt:
  if dp[ls][lt]==dp[ls-1][lt]:
    ls-=1
  elif dp[ls][lt]==dp[ls][lt-1]:
    lt-=1
  else:
    ls-=1;lt-=1
    ans+=s[ls]
print(ans[::-1])
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
*p,= map(float,input().split())
dp = [[0]*(N+1) for _ in range(N+1)]
dp[0][0] = 1

for i in range(N):
	dp[i+1][0] = dp[i][0]*(1-p[i])
	
for i in range(N):
	for h in range(N):
		dp[i+1][h+1] = dp[i][h+1]*(1-p[i]) + dp[i][h]*p[i]

print(sum(dp[-1][N//2+1:]))

Fixed submission:
N = int(input())
*p,= map(float,input().split())
dp = [[0]*(N+1) for _ in range(N+1)]
dp[0][0] = 1

for i in range(N):
	dp[i+1][0] = dp[i][0]*(1-p[i])
	
for i in range(N):
	for h in range(N):
		dp[i+1][h+1] = dp[i][h+1]*(1-p[i]) + dp[i][h]*p[i]

print(sum(dp[-1][N//2+1:]))
Buggy python submission (verdict: Time Limit Exceeded):
n, k, *a = map(int, open(0).read().split())
g = [0] * (k + 1)
for i in range(min(a), k + 1):
	s = set(g[i - x] for x in a if i >= x)
	r = 0
	while r in s:
		r += 1
	g[i] = r
print("First" if g[-1] else "Second")

Fixed submission:
n, k, *a = map(int, open(0).read().split())
g = [0] * (k + 1)
for i in range(min(a), k + 1):
	s = set(g[i - x] for x in a if i >= x)
	r = 0
	while r in s:
		r += 1
	g[i] = r
print("First" if g[-1] else "Second")
Buggy python submission (verdict: Time Limit Exceeded):
def main():
	n, *a = map(int, open(0).read().split())
	dp = [[0] * (n + 1) for _ in range(n + 1)]
	for l in range(n)[::-1]:
		for r in range(n - l)[::-1]:
			dp[l][r] = max(a[l] - dp[l + 1][r], a[n - 1 - r] - dp[l][r + 1])
	print(dp[0][0])

if __name__ == '__main__':
	main()

Fixed submission:
n,*a=map(int,open(0).read().split())
dp=[[0]*(n+1) for _ in range(n+1)]
for l in range(n)[::-1]:
	for r in range(n)[::-1]:
		if l+r<=n-1:
			dp[l][r]=max(a[l]-dp[l+1][r],a[n-1-r]-dp[l][r+1])
print(dp[0][0])

Buggy python submission (verdict: Time Limit Exceeded):
n,*a=map(int,open(0).read().split())
dp=[[0]*(n+1) for _ in range(n+1)]
for l in range(n)[::-1]:
	for r in range(n)[::-1]:
		if l+r<=n-1:
			dp[l][r]=max(a[l]-dp[l+1][r],a[n-1-r]-dp[l][r+1])
print(dp[0][0])

Fixed submission:
n,*a=map(int,open(0).read().split())
dp=[[0]*(n+1) for _ in range(n+1)]
for l in range(n)[::-1]:
	for r in range(n)[::-1]:
		if l+r<=n-1:
			dp[l][r]=max(a[l]-dp[l+1][r],a[n-1-r]-dp[l][r+1])
print(dp[0][0])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**8)
n,*a=map(int,open(0).read().split())
dp=[[0]*(n+1) for _ in range(n+1)]
def dfs(l,r):
	if l+r==n:return 0
	if dp[l][r]:return dp[l][r]
	dp[l][r]=max(a[l]-dfs(l+1,r),a[n-1-r]-dfs(l,r+1))
	return dp[l][r]
print(dfs(0,0))

Fixed submission:
n,*a=map(int,open(0).read().split())
dp=[[0]*(n+1) for _ in range(n+1)]
for l in range(n)[::-1]:
	for r in range(n)[::-1]:
		if l+r<=n-1:
			dp[l][r]=max(a[l]-dp[l+1][r],a[n-1-r]-dp[l][r+1])
print(dp[0][0])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**8)
n,*a=map(int,open(0).read().split())
dp=[[0]*(n+1) for _ in range(n+1)]
def dfs(l,r):
	if l+r==n:return 0
	if dp[l][r]:return dp[l][r]
	dp[l][r]=max(a[l]-dfs(l+1,r),a[n-1-r]-dfs(l,r+1))
	return dp[l][r]
print(dfs(0,0))

Fixed submission:
n,*a=map(int,open(0).read().split())
dp=[[0]*(n+1) for _ in range(n+1)]
for l in range(n)[::-1]:
	for r in range(n)[::-1]:
		if l+r<=n-1:
			dp[l][r]=max(a[l]-dp[l+1][r],a[n-1-r]-dp[l][r+1])
print(dp[0][0])
Buggy python submission (verdict: Time Limit Exceeded):
a=input();c=0
for i,j in enumerate(a):
	c+=(j=="B")*a[i:].count("W")
print(c)

Fixed submission:
import bisect
a=input()
bs=[i for i,j in enumerate(a) if j=="B"]
ws=[i for i,j in enumerate(a) if j=="W"]
cnt=0
for w in ws:
	cnt+=bisect.bisect(bs,w)
print(cnt)

Buggy python submission (verdict: Time Limit Exceeded):
a=input();c=0
for i,j in enumerate(a):
	c+=(j=="B")*a[i:].count("W")
print(c)

Fixed submission:
import bisect
a=input()
bs=[i for i,j in enumerate(a) if j=="B"]
ws=[i for i,j in enumerate(a) if j=="W"]
cnt=0
for w in ws:
	cnt+=bisect.bisect(bs,w)
print(cnt)
Buggy python submission (verdict: Runtime Error):
n,*a=map(int,open(0).read().split());print(asorted((abs(a[i]-sum(a)/n),i)for i in range(n))[0][1])

Fixed submission:
n,*a=map(int,open(0).read().split());print(sorted((abs(a[i]-sum(a)/n),i)for i in range(n))[0][1])
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

n=int(input())
s=input().rsplit()[0]
d=[x=="D" for x in s]
m=[x=="M" for x in s]
c=[x=="C" for x in s]

def calc(k):
	D=M=DM=DMC=0
	for i,fd,fm,fc in zip(range(n),d,m,c):
		if k<=i:
			if d[i-k]:
				D-=1
				DM-=M
			elif m[i-k]:
				M-=1
		if fd:
			D+=1
		elif fm:
			M+=1
			DM+=D
		elif fc:
			DMC+=DM
	return DMC

q=int(input())
ans=[calc(x) for x in map(int,input().split())]
print(*ans,sep="\n")

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

n=int(input())
s=input().rsplit()[0]

def calc(k):
	D=M=DM=DMC=0
	for i in range(n):
		if k<=i:
			if s[i-k]=="D":
				D-=1
				DM-=M
			elif s[i-k]=="M":
				M-=1
		if s[i]=="D":
			D+=1
		elif s[i]=="M":
			M+=1
			DM+=D
		elif s[i]=="C":
			DMC+=DM
	return DMC

q=int(input())
*k,=map(int,input().split())
ans=[calc(x) for x in k]
print(*ans,sep="\n")

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

n=int(input())
s=input().rsplit()[0]

def calc(k):
	D=M=DM=DMC=0
	for i in range(n):
		if k<=i:
			if s[i-k]=="D":
				D-=1
				DM-=M
			elif s[i-k]=="M":
				M-=1
		if s[i]=="D":
			D+=1
		elif s[i]=="M":
			M+=1
			DM+=D
		elif s[i]=="C":
			DMC+=DM
	return DMC

q=int(input())
*k,=map(int,input().split())
ans=[calc(x) for x in k]
print(*ans,sep="\n")

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

n=int(input())
s=input().rsplit()[0]

def calc(k):
	D=M=DM=DMC=0
	for i in range(n):
		if k<=i:
			if s[i-k]=="D":
				D-=1
				DM-=M
			elif s[i-k]=="M":
				M-=1
		if s[i]=="D":
			D+=1
		elif s[i]=="M":
			M+=1
			DM+=D
		elif s[i]=="C":
			DMC+=DM
	return DMC

q=int(input())
*k,=map(int,input().split())
ans=[calc(x) for x in k]
print(*ans,sep="\n")
Buggy python submission (verdict: Runtime Error):
n,m=map(int,input().split())
prev=[];ord=[[]for _ in range(n+1)]
for _ in range(m):
  a,b=map(int,input().split())
  prev.append([a,b])
  ord[a].append(b)
for i in range(n+1):
  if i!=[]:ord[i]=sorted(ord[i])
for [x,y] in prev:
  ind=ord[x].index(y)+1
  print("%06d"%x+"%06d"%ind)
  

Fixed submission:
print(eval(input().replace(" ","+")+"//2"))
Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
prev=[];ord=[[]for _ in range(n+1)]
for _ in range(m):
  a,b=map(int,input().split())
  prev.append([a,b])
  ord[a].append(b)
for i in range(n+1):
  if i!=[]:ord[i]=sorted(ord[i])
for [x,y] in prev:
  ind=ord[x].index(y)+1
  print("%06d"%x+"%06d"%ind)

Fixed submission:
n,m=map(int,input().split());li=[]
for i in range(m):
  li.append(list(map(int,input().split()))+[i])
li.sort()
cac=li[0][0];o=2
li[0][1]=1
for g in li[1:]:
  if g[0]!=cac:
    cac=g[0]
    o=1
  g[1]=o
  o+=1
li.sort(key=lambda x:x[-1])
for g in li:
  print("%06d"%g[0]+"%06d"%g[1])

Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
prev=[];ord=[[]for _ in range(n+1)]
for _ in range(m):
  a,b=map(int,input().split())
  prev.append([a,b])
  ord[a].append(b)
for i in range(n+1):
  if i!=[]:ord[i]=sorted(ord[i])
for [x,y] in prev:
  ind=ord[x].index(y)+1
  print("%06d"%x+"%06d"%ind)

Fixed submission:
n,m=map(int,input().split());li=[]
for i in range(m):
  li.append(list(map(int,input().split()))+[i])
li.sort()
cac=li[0][0];o=2
li[0][1]=1
for g in li[1:]:
  if g[0]!=cac:
    cac=g[0]
    o=1
  g[1]=o
  o+=1
li.sort(key=lambda x:x[-1])
for g in li:
  print("%06d"%g[0]+"%06d"%g[1])

Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
prev=[];ord=[[]for _ in range(n+1)]
for _ in range(m):
  a,b=map(int,input().split())
  prev.append([a,b])
  ord[a].append(b)
for i in range(n+1):
  ord[i]=sorted(ord[i])
for p in prev:
  x,y=p[0],p[1]
  ind=ord[x].index(y)+1
  print("%06d"%x+"%06d"%ind)

Fixed submission:
n,m=map(int,input().split());li=[]
for i in range(m):
  li.append(list(map(int,input().split()))+[i])
li.sort()
cac=li[0][0];o=2
li[0][1]=1
for g in li[1:]:
  if g[0]!=cac:
    cac=g[0]
    o=1
  g[1]=o
  o+=1
li.sort(key=lambda x:x[-1])
for g in li:
  print("%06d"%g[0]+"%06d"%g[1])
Buggy python submission (verdict: Runtime Error):
s=input();print(s[::-(len(s)==3)])

Fixed submission:
s=input();print(s[::1-2*(len(s)>2)])
Buggy python submission (verdict: Runtime Error):
a,b,k=map(int,input().split())
for i in range(k):
  if i%2:
    b//=2
    a+=b
  else:
    a//=2
    b+=a
print(a,b

Fixed submission:
a,b,k=map(int,input().split())
for i in range(k):
  if i%2:b//=2;a+=b
  else:a//=2;b+=a
print(a,b)
Buggy python submission (verdict: Runtime Error):
from fractions import*
n,m=map(int,input().split())
l=n*m//gcd(n,m)
a=[None]*l
b=[None]*l
s,t=input(),input()
for i in range(l):
	if i*n%l==0:
		a[i]=s[i*n//l]
	if i*m%l==0:
		b[i]=t[i*m//l]
for i,j in zip(a,b):
	if None!=i!=j!=None:
		print(-1)
		exit()
print(l)

Fixed submission:
from fractions import*
n,m = map(int,input().split())
g = gcd(n,m)
print(n*m//g if input()[::n//g] == input()[::m//g] else -1)
Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
for i in range(m//n+1)[::-1]:
	if m%i<1:
		print(i)
		exit()

Fixed submission:
n,m=map(int,input().split())
for i in range(m//n+1)[::-1]:
	if m%i<1:
		print(i)
		exit()
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import accumulate

def solve():
	n, X, *x = map(int, open(0).read().split())
	acc = [0] + list(accumulate(x))
	ans = 1 << 60
	for div in range(1, n + 1):
		cost = 0
		phase = 1
		i = n
		while i > 0 and cost < ans:
			cost += (acc[i] - acc[max(i - div, 0)]) * max(5, 2 * phase + 1)
			i -= div
			phase += 1
		cost += (div + n) * X
		if cost < ans:
			ans = cost
	print(ans)

if __name__ == "__main__":
	solve()

Fixed submission:
from itertools import accumulate

def solve():
	n, X, *x = map(int, open(0).read().split())
	acc = [0] + list(accumulate(x))
	ans = 1 << 60
	for div in range(1, n + 1):
		cost = 0
		phase = 1
		i = n
		while i > 0 and cost < ans:
			cost += (acc[i] - acc[max(i - div, 0)]) * max(5, 2 * phase + 1)
			i -= div
			phase += 1
		cost += (div + n) * X
		if cost < ans:
			ans = cost
	print(ans)

if __name__ == "__main__":
	solve()
Buggy python submission (verdict: Runtime Error):
n,k=map(int,input())
if k%2:
  print((n//k)**3)
else:
  l=k//2
  if l%2:
    print(((n+l)//k)**3)
  else:
    print(((n+l)//k)**3 + (n//k)**3)

Fixed submission:
n,k=map(int,input().split())
if k%2:
  print((n//k)**3)
else:
  l=k//2
  print(((n+l)//k)**3+(n//k)**3)
Buggy python submission (verdict: Runtime Error):
class BIT():
	def __init__(self, n):
		self.n = n
		self.bit = [0]*(n+1)
	
	def getsum(self, k):
		ret = 0
		while k:
			ret += self.bit[k]
			k -= k&-k
		return ret
		
	def p_sum(self, i, j):
		return self.getsum(j)-self.getsum(i-1)
		
	def add(self, k, x):
		while k <= n:
			self.bit[k] += x
			k += k&-k

n,m,*t=map(int,open(0).read().split())
q=sorted([(a,b) for a,b in zip(*[iter(t)]*2)],key=lambda x:x[1]-x[0])
bit=BIT(n-1)
c=0
for a,b in q:
	if bit.p_sum(a,b-1)==0:
		bit.add(a,1)
		bit.add(b-1,1)
		c+=1
print(c)

Fixed submission:
def solve():
	n,m,*t=map(int,open(0).read().split())
	r=sorted([(b,a)for a,b in zip(*[iter(t)]*2)])
	c=bef=0
	for b,a in r:
		if a>bef:
			c+=1
			bef=b-1
	print(c)
if __name__=="__main__":solve()
Buggy python submission (verdict: Runtime Error):
a,b=map(int,input().split());print("x*+"[(a*b==15)+(a+b==15)*2]

Fixed submission:
a,b=map(int,input().split());print("x*+"[(a*b==15)+(a+b==15)*2])