Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
import sys
input=lambda: sys.stdin.readline().rstrip()

n,m=map(int,input().split())
A=[int(i)//2 for i in input().split()]
ct=0
s=A[0]
while s:
  if s%2==0:
    s//=2
    ct+=1
  else:
    s=0
chk=True
for i in range(1,n):
  cur=0
  a=A[i]
  while a:
  if a%2==0:
    a//=2
    cur+=1
  else:
    a=0
  if cur!=ct:
    chk=False
    break


def gcd(a,b):
  while b:
    a,b=b,a%b
  return a
if not chk:
  print(0)
else:
  lcm=A[0]
  for i in range(1,n):
    lcm*=A[i]//gcd(lcm,A[i])
  print((m//lcm+1)//2)

Fixed submission:
n,m=map(int,input().split())
A=[int(i)//2 for i in input().split()]

def gcd(a,b):
  while b:
    a,b=b,a%b
  return a

def div2(x):
  ret=0
  while x%2==0:
    ret+=1
    x//=2
  return ret

s=div2(A[0])
chk=True

mul=A[0]
for i in range(1,n):
  if s!=div2(A[i]) or mul>m:
    chk=False
  else:
    mul=mul*A[i]//gcd(mul,A[i])
if not chk:
  print(0)
else:
  print(m//mul-m//(mul*2))

Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
A=[int(i)//2 for i in input().split()]

def gcd(a,b):
  while b:
    a,b=b,a%b
  return a

def div2(x):
  ret=0
  while x%2==0:
    ret+=1
    x//=2
  return ret

s=div2(A[0])
chk=True

mul=A[0]
for i in range(1,n):
  if s!=div2(A[i]):
    chk=False
  mul=mul*A[i]//gcd(mul,A[i])
if not chk:
  print(0)
else:
  print(m//mul-m//(mul*2))

Fixed submission:
n,m=map(int,input().split())
A=[int(i)//2 for i in input().split()]

def gcd(a,b):
  while b:
    a,b=b,a%b
  return a

def div2(x):
  ret=0
  while x%2==0:
    ret+=1
    x//=2
  return ret

s=div2(A[0])
chk=True

mul=A[0]
for i in range(1,n):
  if s!=div2(A[i]) or mul>m:
    chk=False
  else:
    mul=mul*A[i]//gcd(mul,A[i])
if not chk:
  print(0)
else:
  print(m//mul-m//(mul*2))
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
s=input()
A=[int(i) for i in range(10)]
ans=0
import itertools
for a,b,c in itertools.product(A,repeat=3):
  a,b,c=str(a),str(b),str(c)
  chk=0
  for ss in s:
    if chk==0 and ss==a:
      chk=1
    elif chk==1 and ss==b:
      chk=2
    elif chk==2 and ss==c:
      chk=3
  if chk==3:
    ans+=1
print(ans)

Fixed submission:
n=int(input())
s=input()
inf=float("inf")
A=[[inf]*10 for _ in range(n+1)]
for i in reversed(range(n)):
  ss=s[i]
  for j in range(10):
    if j==int(ss):
      A[i][j]=i
    else:
      A[i][j]=A[i+1][j]
ans=0
for x in range(1000):
  x=str(x).zfill(3)
  cur=0
  for xx in x:
    xx=int(xx)
    cur=A[cur][xx]+1
    if cur==inf:
      break
  if cur!=inf:
    ans+=1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
s=input()
def chk(x):
  x=str(x).zfill(3)
  res=False
  cur=0
  xx=x[0]
  for i in range(n):
    ss=s[i]
    if cur<2 and xx==ss:
      cur+=1
      xx=x[cur]
    elif xx==ss:
      res=True
      break
  return res

ans=0
for i in range(1000):
  if chk(i):
    ans+=1
print(ans)  


Fixed submission:
n=int(input())
s=input()
inf=float("inf")
A=[[inf]*10 for _ in range(n+1)]
for i in reversed(range(n)):
  ss=s[i]
  for j in range(10):
    if j==int(ss):
      A[i][j]=i
    else:
      A[i][j]=A[i+1][j]
ans=0
for x in range(1000):
  x=str(x).zfill(3)
  cur=0
  for xx in x:
    xx=int(xx)
    cur=A[cur][xx]+1
    if cur==inf:
      break
  if cur!=inf:
    ans+=1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
x,y=map(int,input().split())
mod=10**9+7
n_max=10**6+1
F,FI=[0]*(n_max+1),[0]*(n_max+1)
F[0],FI[0]=1,1
for i in range(n_max):
  F[i+1]=(F[i]*(i+1))%mod
  FI[i+1]=pow(F[i+1],mod-2,mod)
def comb(x,y):
  return (F[x]*FI[x-y]*FI[y])%mod
a,b=2*y-x,2*x-y
if a<0 or b<0:
  print(0)
elif a%3!=0 or b%3!=0:
  print(0)
else:
  a//=3
  b//=3
  print(comb(a+b,a))


Fixed submission:
x,y=map(int,input().split())
mod=10**9+7
n_max=10**6+1
F,FI=[0]*(n_max+1),[0]*(n_max+1)
F[0],FI[0]=1,1
for i in range(n_max):
  F[i+1]=(F[i]*(i+1))%mod
  FI[i+1]=pow(F[i+1],mod-2,mod)
def comb(x,y):
  return (F[x]*FI[x-y]*FI[y])%mod
a,b=2*y-x,2*x-y
if a<0 or b<0:
  print(0)
elif a%3!=0 or b%3!=0:
  print(0)
else:
  a//=3
  b//=3
  print(comb(a+b,a))
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input=sys.stdin.readline
n,t=map(int,input().split())
AB=[]
for i in range(n):
  a,b=map(int,input().split())
  AB.append((a,b))

def f(m):
  dp=[[0]*(t) for _ in range(n+1)]
  for i in range(n):
    if i==m:
      a,b=AB[i]
      add=b
      for j in range(t):
        dp[i+1][j]=dp[i][j]
    else:
      a,b=AB[i]
      for j in range(t):
        if j>=a:
          dp[i+1][j]=max(dp[i][j-a]+b,dp[i][j],dp[i+1][j-1])
        else:
          dp[i+1][j]=max(dp[i][j],dp[i+1][j-1])
  return dp[n][t-1]+add
ans=0
for i in range(n):
  ans=max(ans,f(i))
print(ans)


Fixed submission:
import sys
input=sys.stdin.readline
n,t=map(int,input().split())
AB=[]
for i in range(n):
  a,b=map(int,input().split())
  AB.append((a,b))
AB.sort(key=lambda x:x[0])
ans=0
dp=[[0]*(t) for _ in range(n+1)]
for i in range(n-1):
  a,b=AB[i]
  for j in range(t):
    if j>=a:
      dp[i+1][j]=max(dp[i][j-a]+b,dp[i][j],dp[i+1][j-1])
    else:
      dp[i+1][j]=max(dp[i][j],dp[i+1][j-1])
  ans=max(ans,dp[i+1][t-1]+AB[i+1][1])

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n,k=map(int,input().split())
A=[int(i) for i in input().split()]
F=[int(i) for i in input().split()]
A.sort()
F.sort()

def chk(x):
  ct=0
  for i in range(n):
    a,f=A[i],F[-i-1]
    ct+=max(0,a-x//f)
    if ct>k:
      return False
  if ct<=k:
    return True
  else:
    return False
l=0
r=0
for i in range(n):
  r=max(r,A[i]*F[-i-1])

while r-l>1:
  m=(l+r)//2
  if chk(m):
    r=m
  else:
    l=m

if chk(l):
  print(l)
else:
  print(r)


Fixed submission:
n,k=map(int,input().split())
A=[int(i) for i in input().split()]
F=[int(i) for i in input().split()]
A.sort()
F.sort()

def chk(x):
  ct=0
  for i in range(n):
    a,f=A[i],F[-i-1]
    ct+=max(0,a-x//f)
    if ct>k:
      return False
  if ct<=k:
    return True
  else:
    return False
l=0
r=0
for i in range(n):
  r=max(r,A[i]*F[-i-1])

while r-l>1:
  m=(l+r)//2
  if chk(m):
    r=m
  else:
    l=m

if chk(l):
  print(l)
else:
  print(r)

Buggy python submission (verdict: Time Limit Exceeded):
n,k=map(int,input().split())
A=[int(i) for i in input().split()]
F=[int(i) for i in input().split()]
A.sort()
F.sort()

def chk(x):
  ct=0
  for i in range(n):
    a,f=A[i],F[-i-1]
    ct+=max(0,a-x//f)
  if ct<=k:
    return True
  else:
    return False


l,r=0,A[-1]*F[-1]
while r-l>1:
  m=(l+r)//2
  if chk(m):
    r=m
  else:
    l=m

if chk(l):
  print(l)
else:
  print(r)

Fixed submission:
n,k=map(int,input().split())
A=[int(i) for i in input().split()]
F=[int(i) for i in input().split()]
A.sort()
F.sort()

def chk(x):
  ct=0
  for i in range(n):
    a,f=A[i],F[-i-1]
    ct+=max(0,a-x//f)
    if ct>k:
      return False
  if ct<=k:
    return True
  else:
    return False
l=0
r=0
for i in range(n):
  r=max(r,A[i]*F[-i-1])

while r-l>1:
  m=(l+r)//2
  if chk(m):
    r=m
  else:
    l=m

if chk(l):
  print(l)
else:
  print(r)
Buggy python submission (verdict: Runtime Error):
import heapq
n,m,l=map(int,input().split())
edge=[[] for i in range(n)]
for i in range(m):
  a,b,c=map(int,input().split())
  edge[a-1].append([c,b-1])
  edge[b-1].append([c,a-1])

def f(s):
  d=[float("inf")]*n
  used=[True]*n
  d[s]=0
  used[s]=False
  edgelist=[]
  ans=0
  cur=l
  for c,e in edge[s]:
    heapq.heappush(edgelist,c*10**3+e)
  while edgelist:
    minedge=heapq.heappop(edgelist)
    v=minedge[0]%(10**3)
    ans,cur=minedge[0]//(10**13),(minedge[0]%(10**13))//(10**3)
    used[v]=False
    d[v]=ans
    
    for e in edge[v]:
      if used[e[1]]:
        if e[0]>l:
          continue
        elif e[0]+cur>l:
          heapq.heappush(edgelist,(ans+1)*10**13+e[0]*10**3+e[1])
        else:
          heapq.heappush(edgelist,(ans)*10**13+(e[0]+cur)*10**3+e[1])
  return d
Ans=[[] for i in range(n)]
for i in range(n):
  Ans[i]=f(i)
q=int(input())
for _ in range(q):
  s,t=map(int,input().split())
  print(-1 if Ans[s-1][t-1]==float("inf") else Ans[s-1][t-1])

Fixed submission:

from scipy.sparse.csgraph import floyd_warshall
n,m,l=map(int,input().split())
table=[[0]*n for i in range(n)]
for i in range(m):
    a,b,c=map(int,input().split())
    table[a-1][b-1]=c
    table[b-1][a-1]=c
d=floyd_warshall(csgraph=table, directed=False, return_predecessors=False)

table2=[[0]*n for i in range(n)]
for i in range(n):
  for j in range(i+1,n):
    if d[i][j]<=l:
      table2[i][j]=1
      table2[j][i]=1
d2=floyd_warshall(csgraph=table2, directed=False, return_predecessors=False)
q=int(input())
for _ in range(q):
  s,t=map(int,input().split())
  if d2[s-1][t-1]==float("inf"):
    print(-1)
  else:
    print(int(d2[s-1][t-1])-1)
Buggy python submission (verdict: Runtime Error):
s=input()
k=int(input())
ans=0
chg=0
for i in range(1,len(s)):
  if chg==0 and s[i-1]==s[i]:
    ans+=1
    chg=1
  else:
    chg=0
ans2=1
chg2=1
for i in range(1,len(s)):
  if chg==0 and s[i-1]==s[i]:
    ans2+=1
    chg2=1
  else:
    chg2=0
if s[0]!=s[1]:
  print(k*ans)
else:
  print(k*min(ans,ans2))



Fixed submission:
s=input()
k=int(input())
if len(s)==1:
  print(k//2)
else:
  ans=0
  chg=0
  for i in range(1,len(s)):
    if chg==0 and s[i-1]==s[i]:
      ans+=1
      chg=1
    else:
      chg=0
  ans2=1
  chg2=1
  for i in range(1,len(s)):
    if chg2==0 and s[i-1]==s[i]:
      ans2+=1
      chg2=1
    else:
      chg2=0
  if s[0]!=s[-1] or chg==1:
    print(k*ans)
  elif chg2==0:
    print((k-1)*ans2+ans)
  else:
    print(ans*((k+1)//2)+ans2*(k//2))
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
table=[[float("inf")]*n for i in range(n)]
for i in range(n):
  s=input()
  for j in range(n):
    if s[j]=="1":
      table[i][j]=1
    
def warshall_floyd(d):
  for k in range(n):
    for i in range(n):
      for j in range(n):
        if d[i][k]+d[k][j]<d[i][j]:
          d[i][j]=d[i][k]+d[k][j]
        if d[i][j]<float("inf") and d[i][k]+d[k][j]<float("inf") and d[i][j]%2!=(d[i][k]+d[k][j])%2:
          return False
  return d

d=warshall_floyd(table)

if not d:
  print(-1)
else:
  ans=0
  for i in range(n):
    for j in range(i+1,n):
      ans=max(ans,d[i][j]+1)
  
  print(ans)

Fixed submission:
n=int(input())
inf=float("inf")
table=[[inf]*n for i in range(n)]
for i in range(n):
  s=input()
  for j in range(n):
    if s[j]=="1":
      table[i][j]=1
    
def warshall_floyd(d):
  for k in range(n):
    for i in range(n):
      for j in range(n):
        if d[i][k]!=inf and d[k][j]!=inf:
          d[i][j]=min(d[i][j],d[i][k]+d[k][j])
          if d[i][j]<float("inf") and d[i][j]%2!=(d[i][k]+d[k][j])%2:
            return False
  return d

d=warshall_floyd(table)

if not d:
  print(-1)
else:
  ans=0
  for i in range(n):
    for j in range(i+1,n):
      ans=max(ans,d[i][j]+1)
  
  print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
table=[[0]*n for i in range(n)]
for i in range(n):
  s=input()
  for j in range(n):
    if s[j]=="1":
      table[i][j]=1
    else:
      table[i][j]=float("inf")
def warshall_floyd(d):
  for k in range(n):
    for i in range(n):
      for j in range(n):
        if d[i][j]==float("inf") or d[i][k]+d[k][j]==float("inf"):
          d[i][j]=min(d[i][j],d[i][k]+d[k][j])
        else:
          if d[i][j]%2!=(d[i][k]+d[k][j])%2:
            return False
          else:
            d[i][j]=min(d[i][j],d[i][k]+d[k][j])
  return d

d=warshall_floyd(table)

if not d:
  print(-1)
else:
  ans=0
  for i in range(n):
    for j in range(i+1,n):
      ans=max(ans,d[i][j]+1)
  
  print(ans)

Fixed submission:
n=int(input())
inf=float("inf")
table=[[inf]*n for i in range(n)]
for i in range(n):
  s=input()
  for j in range(n):
    if s[j]=="1":
      table[i][j]=1
    
def warshall_floyd(d):
  for k in range(n):
    for i in range(n):
      for j in range(n):
        if d[i][k]!=inf and d[k][j]!=inf:
          d[i][j]=min(d[i][j],d[i][k]+d[k][j])
          if d[i][j]<float("inf") and d[i][j]%2!=(d[i][k]+d[k][j])%2:
            return False
  return d

d=warshall_floyd(table)

if not d:
  print(-1)
else:
  ans=0
  for i in range(n):
    for j in range(i+1,n):
      ans=max(ans,d[i][j]+1)
  
  print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
A=[]
for i in range(m):
  a,b=map(int,input().split())
  C=[int(i) for i in input().split()]
  x=0
  for c in C:
    x|=(1<<(c-1))
  A.append((a,x))
DP=[float("inf")]*(2**n)
DP[0]=0
for i in range(m):
  a,x=A[i]
  for j in range(2**n):

    DP[j|x]=min(DP[j|x],DP[j]+a)

print(-1 if DP[2**n-1]==float("inf") else DP[2**n-1])


Fixed submission:
n,m=map(int,input().split())
A=[]
for i in range(m):
  a,b=map(int,input().split())
  C=[int(i) for i in input().split()]
  x=0
  for c in C:
    x|=(1<<(c-1))
  A.append((a,x))
DP=[float("inf")]*(2**n)
DP[0]=0
for i in range(m):
  a,x=A[i]
  for j in range(2**n):

    DP[j|x]=min(DP[j|x],DP[j]+a)

print(-1 if DP[2**n-1]==float("inf") else DP[2**n-1])
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
P=[int(i) for i in input().split()]
n_max=10**5
nn=n_max.bit_length()+1
BIT=[0]*(2**nn)
BIT.insert(0,0)
def bitsum(BIT,i):
  s=0
  while i>0:
    s+=BIT[i]
    i-=i&(-i)
  return s
def bitadd(BIT,i,x):
  while i<=2**nn:
    BIT[i]+=x
    i+=i&(-i)
  return BIT
def bitlb(BIT,s):
  if s<=0:
    return 0
  else:
    ret=0
    k=2**nn
    while k>0:
      if k+ret<=2**nn and BIT[k+ret]<s:
        s-=BIT[k+ret]
        ret+=k
      k//=2
    return ret+1
D=dict()
for i in range(n):
  D[P[i]]=i+1
PP=sorted(P,reverse=True)
bitadd(BIT,D[PP[0]],1)
ans=0
for i in range(1,n):
  cur=D[PP[i]]
  bitadd(BIT,cur,1)
  tot=bitsum(BIT,cur)
  l2,l1,r1,r2=bitlb(BIT,tot-2),bitlb(BIT,tot-1),min(n+1,bitlb(BIT,tot+1)),min(n+1,bitlb(BIT,tot+2))
  add=PP[i]*((-l1+cur)*(r2-r1)+(l1-l2)*(r1-cur))
  ans+=add
print(ans)

Fixed submission:
n=int(input())
P=[int(i) for i in input().split()]
n_max=10**5
nn=n_max.bit_length()+1
BIT=[0]*(2**nn)
BIT.insert(0,0)
def bitsum(BIT,i):
  s=0
  while i>0:
    s+=BIT[i]
    i-=i&(-i)
  return s
def bitadd(BIT,i,x):
  while i<=2**nn:
    BIT[i]+=x
    i+=i&(-i)
  return BIT
def bitlb(BIT,s):
  if s<=0:
    return 0
  else:
    ret=0
    k=2**nn
    while k>0:
      if k+ret<=2**nn and BIT[k+ret]<s:
        s-=BIT[k+ret]
        ret+=k
      k//=2
    return ret+1
D=dict()
for i in range(n):
  D[P[i]]=i+1
PP=sorted(P,reverse=True)
bitadd(BIT,D[PP[0]],1)
ans=0
for i in range(1,n):
  cur=D[PP[i]]
  bitadd(BIT,cur,1)
  tot=bitsum(BIT,cur)
  l2,l1,r1,r2=bitlb(BIT,tot-2),bitlb(BIT,tot-1),min(n+1,bitlb(BIT,tot+1)),min(n+1,bitlb(BIT,tot+2))
  add=PP[i]*((-l1+cur)*(r2-r1)+(l1-l2)*(r1-cur))
  ans+=add
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
n=int(input())
A=[]
for i in range(n):
  A.append([int(i) for i in input().split()])
nn=n*(n-1)//2
F=[[0]*(n+1) for _ in range(n+1)]
cur=0
for i in range(1,n):
  for j in range(i+1,n+1):
    F[i][j]=cur
    F[j][i]=cur
    cur+=1
Edge=[[] for _ in range(nn)]
Deg=[0]*nn
for i in range(n):
  s=F[i+1][A[i][0]]
  for j in range(1,n-1):
    t=F[i+1][A[i][j]]
    Edge[s].append(t)
    Deg[t]+=1
    s=t
ans=0
S=[i for i in range(nn) if Deg[i]==0]
D=deque()
DD=deque(S)
while DD:
  D=DD
  DD=deque()
  while D:
    d=D.popleft()
    for g in Edge[d]:
      Deg[g]-=1
      if Deg[g]==0:
        DD.append(g)
        S.append(g)
  ans+=1
print(-1 if len(S)<nn else ans)

Fixed submission:
from collections import deque
n=int(input())
A=[]
for i in range(n):
  A.append([int(i) for i in input().split()])
nn=n*(n-1)//2
F=[[0]*(n+1) for _ in range(n+1)]
cur=0
for i in range(1,n):
  for j in range(i+1,n+1):
    F[i][j]=cur
    F[j][i]=cur
    cur+=1
Edge=[[] for _ in range(nn)]
Deg=[0]*nn
for i in range(n):
  s=F[i+1][A[i][0]]
  for j in range(1,n-1):
    t=F[i+1][A[i][j]]
    Edge[s].append(t)
    Deg[t]+=1
    s=t
ans=0
S=[i for i in range(nn) if Deg[i]==0]
D=deque()
DD=deque(S)
while DD:
  D=DD
  DD=deque()
  while D:
    d=D.popleft()
    for g in Edge[d]:
      Deg[g]-=1
      if Deg[g]==0:
        DD.append(g)
        S.append(g)
  ans+=1
print(-1 if len(S)<nn else ans)
Buggy python submission (verdict: Runtime Error):
n=int(input())
XY=[]
for i in range(n):
  XY.append([int(i) for i in input().split()])
ans=0
def dis(X):
  return (X[0]**2+X[1]**2)**0.5
for i in range(n):
  A=[dis(XY[i])]
  x1,y1=XY[i][0],XY[i][1]
  for j in range(n):
    if j==i:
      continue
    else:
      x2,y2=XY[j][0],XY[j][1]
      A.append((x1*x2+y1*y2)/A[0])
  ans1,ans2=0,0
  for k in range(n):
    if A[k]>=0:
      ans1+=A[k]
    else:
      ans2-=A[k]
  ans=max([ans,ans1,ans2])
print(ans)



Fixed submission:
import math
n=int(input())
def f(x,y):
  return math.atan2(y,x)
  
XY=[]
for i in range(n):
  x,y=map(int,input().split())
  XY.append((x,y,f(x,y)))
XY.sort(key=lambda x:x[2])

def dis(x,y):
  return (x**2+y**2)**0.5
ans=0
for i in range(n):
  for j in range(1,n+1):
    x,y=0,0
    if i+j<=n:
      for k in range(i,i+j):
        x+=XY[k][0]
        y+=XY[k][1]
      ans=max(ans,dis(x,y))
    else:
      for k in range(i,n):
        x+=XY[k][0]
        y+=XY[k][1]
      for k in range(j-(n-i)):
        x+=XY[k][0]
        y+=XY[k][1]
      ans=max(ans,dis(x,y))
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
p=int(input())
A=[int(i) for i in input().split()]
B=[0]*p

P=[[0]*p for _ in range(p)]
for i in range(1,p): 
  for j in range(1,p):
    if j==1:
      P[i][j]=i
    else:
      P[i][j]=(P[i][j-1]*i)%p

for i in range(p):
  a=A[i]
  B[0]-=a
  for j in range(1,p):
    B[j]-=a*P[i][j]
    if j==p-1:
      B[j]+=a
B=B[::-1]
for i in range(p):
  B[i]%=p
print(*B)

Fixed submission:
import sys
input = sys.stdin.readline
p=int(input())
A=[int(i) for i in input().split()]
B=[0]*p

P=[[0]*p for _ in range(p)]
for i in range(1,p): 
  for j in range(1,p):
    if j==1:
      P[i][j]=i
    else:
      P[i][j]=(P[i][j-1]*i)%p

for i in range(p):
  a=A[i]
  B[0]-=a
  for j in range(1,p):
    B[j]-=a*P[i][j]
    if j==p-1:
      B[j]+=a
B=B[::-1]
for i in range(p):
  B[i]%=p
print(*B)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
p=int(input())
A=[int(i) for i in input().split()]
mod=p
B=[0]*p
for i in range(p):
  c=1
  B[0]-=A[i]
  for j in range(1,p):
    c*=i
    B[j]-=A[i]*c
    if j==p-1:
      B[j]+=A[i]
B=B[::-1]
for i in range(p):
  B[i]=B[i]%mod
print(*B)

Fixed submission:
import sys
input = sys.stdin.readline
p=int(input())
A=[int(i) for i in input().split()]
B=[0]*p

P=[[0]*p for _ in range(p)]
for i in range(1,p): 
  for j in range(1,p):
    if j==1:
      P[i][j]=i
    else:
      P[i][j]=(P[i][j-1]*i)%p

for i in range(p):
  a=A[i]
  B[0]-=a
  for j in range(1,p):
    B[j]-=a*P[i][j]
    if j==p-1:
      B[j]+=a
B=B[::-1]
for i in range(p):
  B[i]%=p
print(*B)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
p=int(input())
A=[int(i) for i in input().split()]
mod=p
B=[0]*p
for i in range(p):
  c=1
  B[0]-=A[i]
  for j in range(1,p):
    c*=i
    B[j]-=A[i]*c
    if j==p-1:
      B[j]+=A[i]
B=B[::-1]
for i in range(p):
  B[i]=B[i]%mod
print(*B)

Fixed submission:
import sys
input = sys.stdin.readline
p=int(input())
A=[int(i) for i in input().split()]
B=[0]*p

P=[[0]*p for _ in range(p)]
for i in range(1,p): 
  for j in range(1,p):
    if j==1:
      P[i][j]=i
    else:
      P[i][j]=(P[i][j-1]*i)%p

for i in range(p):
  a=A[i]
  B[0]-=a
  for j in range(1,p):
    B[j]-=a*P[i][j]
    if j==p-1:
      B[j]+=a
B=B[::-1]
for i in range(p):
  B[i]%=p
print(*B)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
p=int(input())
A=[int(i) for i in input().split()]
mod=p
B=[0]*p
for i in range(p):
  C=[1]*p
  B[0]=(B[0]-A[i])%mod
  for j in range(1,p):
    C[j]=(C[j-1]*i)%mod
    B[j]=(B[j]-A[i]*C[j])%mod
    if j==p-1:
      B[j]=(B[j]+A[i])%mod
B=B[::-1]
print(*B)
    


Fixed submission:
import sys
input = sys.stdin.readline
p=int(input())
A=[int(i) for i in input().split()]
B=[0]*p

P=[[0]*p for _ in range(p)]
for i in range(1,p): 
  for j in range(1,p):
    if j==1:
      P[i][j]=i
    else:
      P[i][j]=(P[i][j-1]*i)%p

for i in range(p):
  a=A[i]
  B[0]-=a
  for j in range(1,p):
    B[j]-=a*P[i][j]
    if j==p-1:
      B[j]+=a
B=B[::-1]
for i in range(p):
  B[i]%=p
print(*B)
Buggy python submission (verdict: Runtime Error):
n=int(input())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]
ct=0
for i in range(n):
  if i+1!=P[i]:
    ct+=1
print("YES" if ct<=2 else "NO")

Fixed submission:
n=int(input())
P=[int(i) for i in input().split()]
ct=0
for i in range(n):
  if i+1!=P[i]:
    ct+=1
print("YES" if ct<=2 else "NO")
Buggy python submission (verdict: Runtime Error):
def primes(x):
  is_prime = [True] * (x + 1)
  is_prime[0] = False
  is_prime[1] = False
  for i in range(2, int(x**0.5) + 1):
    if not is_prime[i]:
      continue
    for j in range(i * 2, x + 1, i):
      is_prime[j] = False
  return [i for i in range(x + 1) if is_prime[i]]

n=int(input())
P=primes(n)
A=[int(i) for i in input().split()]
Ans=[]
C=[False]*n
for i in reversed(range(n)):
  if A[i]==1:    
    if 2*(i+1)>n:
      Ans.append(i+1)
      C[i]=True
    else:
      c=1
      j=0
      while P[j]*(i+1)<=n:
        if C[P[j]*(i+1)-1]==True:
          c^=1
        j+=1
      if c==1:
        Ans.append(i+1)
        C[i]=True
  elif A[i]==1:    
    c=0
    j=0
    while P[j]*(i+1)<=n:
      if C[P[j]*(i+1)-1]==True:
        c^=1
      j+=1
    if c==1:
      Ans.append(i+1)
      C[i]=True
if len(Ans)==0:
  print(0)
else:
  print(len(Ans))
  Ans.sort()
  print(*Ans)

Fixed submission:
n=int(input())

A=[int(i) for i in input().split()]
Ans=[]
C=[False]*n
for i in reversed(range(n)):
  if A[i]==1:    
    if 2*(i+1)>n:
      Ans.append(i+1)
      C[i]=True
    else:
      c=0
      j=2
      while j*(i+1)<=n:
        if C[j*(i+1)-1]==True:
          c^=1
        j+=1
      if c==0:
        Ans.append(i+1)
        C[i]=True
        
  elif A[i]==0:    
    c=0
    j=2
    while j*(i+1)<=n:
      if C[j*(i+1)-1]==True:
        c^=1
      j+=1
    if c==1:
      Ans.append(i+1)
      C[i]=True
      
if len(Ans)==0:
  print(0)
else:
  print(len(Ans))
  Ans.sort()
  print(*Ans)