Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
n,k=map(int,input().split())
a=list(map(int,input().split()))
f=list(map(int,input().split()))
a=sorted(a)
f=sorted(f,reverse=True)


def is_lessthanK(X):
  ans=0
  for i in range(n):
    if a[i]*f[i]>X:
      ans+=a[i]-X//f[i]
    if ans > k:
      return False
  return True


ng=-1
ok=a[-1]*f[0]
while ok-ng>1:
  mid=(ok+ng)//2
  if is_lessthanK(mid):
    ok=mid
  else:
    ng=mid
print(ok)



Fixed submission:
n,k=map(int,input().split())
a=list(map(int,input().split()))
f=list(map(int,input().split()))
a=sorted(a)
f=sorted(f,reverse=True)


def is_lessthanK(X):
  ans=0
  for A,F in zip(a,f):
    if A*F>X:
      ans+=A-X//F
    if ans > k:
      return False
  return True


ng=-1
ok=a[-1]*f[0]
while ok-ng>1:
  mid=(ok+ng)//2
  if is_lessthanK(mid):
    ok=mid
  else:
    ng=mid
print(ok)

Buggy python submission (verdict: Time Limit Exceeded):
n,k=map(int,input().split())
a=list(map(int,input().split()))
f=list(map(int,input().split()))
a=sorted(a)
f=sorted(f,reverse=True)


def is_lessthanK(X):
  ans=0
  for i in range(n):
    ans+=max(0,a[i]-X//f[i])
    if ans > k:
      return False
  return True


ng=-1
ok=10**13
while ok-ng>1:
  mid=(ok+ng)//2
  if is_lessthanK(mid):
    ok=mid
  else:
    ng=mid
print(ok)



Fixed submission:
n,k=map(int,input().split())
a=list(map(int,input().split()))
f=list(map(int,input().split()))
a=sorted(a)
f=sorted(f,reverse=True)


def is_lessthanK(X):
  ans=0
  for A,F in zip(a,f):
    if A*F>X:
      ans+=A-X//F
    if ans > k:
      return False
  return True


ng=-1
ok=a[-1]*f[0]
while ok-ng>1:
  mid=(ok+ng)//2
  if is_lessthanK(mid):
    ok=mid
  else:
    ng=mid
print(ok)

Buggy python submission (verdict: Time Limit Exceeded):
n,k=map(int,input().split())
a=list(map(int,input().split()))
f=list(map(int,input().split()))
a=sorted(a)
f=sorted(f,reverse=True)

def is_lessthanK(X):
  ans=0
  for i in range(n):
    ans+=max(0,a[i]-X//f[i])
  return ans<=k

ng=-1
ok=10**13
while ok-ng>1:
  mid=(ok+ng)//2
  if is_lessthanK(mid):
    ok=mid
  else:
    ng=mid
print(ok)



Fixed submission:
n,k=map(int,input().split())
a=list(map(int,input().split()))
f=list(map(int,input().split()))
a=sorted(a)
f=sorted(f,reverse=True)


def is_lessthanK(X):
  ans=0
  for A,F in zip(a,f):
    if A*F>X:
      ans+=A-X//F
    if ans > k:
      return False
  return True


ng=-1
ok=a[-1]*f[0]
while ok-ng>1:
  mid=(ok+ng)//2
  if is_lessthanK(mid):
    ok=mid
  else:
    ng=mid
print(ok)
Buggy python submission (verdict: Runtime Error):
import numpy as np
from scipy.sparse.csgraph import floyd_warshall

N,M,L=map(int,input().split())
INF = 1 << 31
dist=np.array([[INF for _ in range(N)] for _ in range(N)])

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

dist = floyd_warshall(dist)

for i in range(N):
  for j in range(N):
    if dist[i][j]<=L:
      dist[i][j]=1
    else:
      dist[i][j]=0

dist = floyd_warshall(dist)
#dist[dist==INF]=0
#dist=dist.astype(int)
#print(dist)

Q=int(input())
ans=[0]*Q
for q in range(Q):
  s,t=map(int,input().split())
  s-=1
  t-=1
  ans[q]=int(dist[s][t]-1)

print(*ans,sep='\n')



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

N,M,L=map(int,input().split())
INF = 1 << 31
dist=np.array([[INF for _ in range(N)] for _ in range(N)])

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

dist = floyd_warshall(dist)

for i in range(N):
  for j in range(N):
    if dist[i][j]<=L:
      dist[i][j]=1
    else:
      dist[i][j]=INF

dist = floyd_warshall(dist)
dist[dist==INF]=0
#dist=dist.astype(int)
#print(dist)

Q=int(input())
ans=[0]*Q
for q in range(Q):
  s,t=map(int,input().split())
  s-=1
  t-=1
  ans[q]=int(dist[s][t]-1)

for a in ans:
  print(-1 if a==INF else a)
Buggy python submission (verdict: Runtime Error):
w=['Sunny', 'Cloudy', 'Rainy']
print(w[(w.index(input)+1)%3])

Fixed submission:
w=['Sunny', 'Cloudy', 'Rainy']
print(w[(w.index(input())+1)%3])
Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
a=list(map(int,input().split()))
for i in range(m):
  a[a.index(max(a))]//=2
print(sum(a))


Fixed submission:
import bisect

n,m=map(int,input().split())
a=sorted(list(map(int,input().split())))
for i in range(m):
  t=a[-1]
  t//=2
  a.pop()
  bisect.insort_left(a,t)
  #print(i,a)
print(sum(a))

Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
a=list(map(int,input().split()))
for i in range(m):
  a[a.index(max(a))]//=2
print(sum(a))


Fixed submission:
import bisect

n,m=map(int,input().split())
a=sorted(list(map(int,input().split())))
for i in range(m):
  t=a[-1]
  t//=2
  a.pop()
  bisect.insort_left(a,t)
  #print(i,a)
print(sum(a))

Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
a=list(map(int,input().split()))
for i in range(m):
  a[a.index(max(a))]//=2
print(sum(a))


Fixed submission:
import bisect

n,m=map(int,input().split())
a=sorted(list(map(int,input().split())))
for i in range(m):
  t=a[-1]
  t//=2
  a.pop()
  bisect.insort_left(a,t)
  #print(i,a)
print(sum(a))

Buggy python submission (verdict: Time Limit Exceeded):
import bisect

n,m=map(int,input().split())
a=sorted(list(map(int,input().split())))
for i in range(m):
  t=a[-1]
  t//=2
  a.pop()
  bisect.insort_left(a,t)
  #print(i,a)
print(sum(a))


Fixed submission:
import bisect

n,m=map(int,input().split())
a=sorted(list(map(int,input().split())))
for i in range(m):
  t=a[-1]
  t//=2
  a.pop()
  bisect.insort_left(a,t)
  #print(i,a)
print(sum(a))
Buggy python submission (verdict: Time Limit Exceeded):
import copy

def main():
  n,k=map(int,input().split())
  s=input()
  # maked group
  t=[]
  t.append(s[0])
  x=s[0]
  for i in range(1,n):
    if x!=s[i]:
      t.append(s[i])
      x=s[i]
  #print(t)
  
  j=0
  while j<k:
    if len(t)<=2:
      print(n-1)
      exit(0)
    t=copy.copy(t[2:])
    j+=1
    
  print(n-1-(len(t)-1))

  
if __name__=='__main__':
  main()

Fixed submission:
from collections import deque

def main():
  n,k=map(int,input().split())
  s=input()
  # maked group
  t=[]
  t.append(s[0])
  x=s[0]
  for i in range(1,n):
    if x!=s[i]:
      t.append(s[i])
      x=s[i]
  #print(t)
  
  j=0
  t=deque(t)
  while j<k:
    if len(t)<=2:
      print(n-1)
      exit(0)
    t.popleft()
    t.popleft()
    j+=1
    
  print(n-1-(len(t)-1))

  
if __name__=='__main__':
  main()
Buggy python submission (verdict: Runtime Error):
def dfs(_v, _u):
  for u in v[_v]:
    if u==_u: continue;
    ans[u]+=ans[_v]
    dfs(u, _v)
        
  
def main():
  for i in range(n-1):
    a,b=map(lambda x:int(x)-1, input().split())
    v[a].append(b)
    v[b].append(a)
  
  for i in range(q):
    p,x=map(lambda x:int(x)-1, input().split())
    ans[p]+=x+1
  
  dfs(0,-1)
  
  print(*ans, sep=' ')
  
if __name__=='__main__':
  n,q=map(int,input().split())
  ans=[0]*n
  v=[[]*n for i in range(n)]
  main()

Fixed submission:
from collections import deque


def main():
  n,q=map(int,input().split())
  node=[[]*n for i in range(n)]
  for i in range(n-1):
    a,b=map(lambda x:int(x)-1,input().split())
    node[b].append(a)
    node[a].append(b)
  
  ans=[0]*n
  for i in range(q):
    p,x=map(int,input().split())
    p-=1
    ans[p]+=x

  root=[0]*n
  edge=[[]*n for i in range(n)]
  root[0]=0
  q=deque([0])
  visited=[False]*n
  visited[0]=True
  
  while q:
    r=q.popleft()
    for e in node[r]:
      if not visited[e]:
        visited[e]=True
        q.append(e)
        root[e]=r
        edge[r].append(e)
  
  
  p=[0]*n
  q=deque(edge[0])
  visited=[False]*n
  while q:
    e=q.popleft()
    p[e]=p[root[e]]+1
    for e2 in edge[e]:
      if not visited[e2]:
        visited[e2]=True
        q.append(e2)
  
  p=sorted(enumerate(p), key=lambda x:x[1])
  for i in range(1,n):
    e=p[i][0]
    r=root[e]
    ans[e]+=ans[r]
    
  print(*ans,sep=' ')


if __name__=='__main__':
  main()

Buggy python submission (verdict: Runtime Error):
def main():
  n,q=map(int,input().split())
  g=[[] for i in range(n)]
  g[0]=[0]
  for i in range(n-1):
    a,b=map(lambda x:int(x)-1,input().split())
    g[b].append(a)
    
  ans=[0]*n
  for i in range(q):
    p,x=map(int,input().split())
    p-=1
    ans[p]+=x
  
  g=sorted(enumerate(g), key=lambda x:(x[1][0]))
  #print(g)
  for i in range(1,n):
    e,rs=g[i][0],g[i][1]
    for r in rs:
      ans[e]+=ans[r]
    
  print(*ans,sep=' ')


if __name__=='__main__':
  main()

Fixed submission:
from collections import deque


def main():
  n,q=map(int,input().split())
  node=[[]*n for i in range(n)]
  for i in range(n-1):
    a,b=map(lambda x:int(x)-1,input().split())
    node[b].append(a)
    node[a].append(b)
  
  ans=[0]*n
  for i in range(q):
    p,x=map(int,input().split())
    p-=1
    ans[p]+=x

  root=[0]*n
  edge=[[]*n for i in range(n)]
  root[0]=0
  q=deque([0])
  visited=[False]*n
  visited[0]=True
  
  while q:
    r=q.popleft()
    for e in node[r]:
      if not visited[e]:
        visited[e]=True
        q.append(e)
        root[e]=r
        edge[r].append(e)
  
  
  p=[0]*n
  q=deque(edge[0])
  visited=[False]*n
  while q:
    e=q.popleft()
    p[e]=p[root[e]]+1
    for e2 in edge[e]:
      if not visited[e2]:
        visited[e2]=True
        q.append(e2)
  
  p=sorted(enumerate(p), key=lambda x:x[1])
  for i in range(1,n):
    e=p[i][0]
    r=root[e]
    ans[e]+=ans[r]
    
  print(*ans,sep=' ')


if __name__=='__main__':
  main()
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=[0]+list(map(int,input().split()))

m=0
ans=[]
c=[0]*(n+1)
for i in reversed(range(1,n+1)):
  if a[i]%2!=c[i]%2:
    m+=1
    ans.append(i)
    j=1
    r=set()
    while j*j<=i:
      if i%j==0:
        r.add(j)
        r.add(i//j)
      j+=1
    for j in r:
      c[j]+=1
      c[j]%=2
        
print(m)
print(*sorted(ans))       

Fixed submission:
n=int(input())
a=[0]+list(map(int,input().split()))

m=0
ans=[]
c=[0]*(n+1)
for i in reversed(range(1,n+1)):
  if a[i]%2!=c[i]%2:
    m+=1
    ans.append(i)
    j=1
    r=set()
    while j*j<=i:
      if i%j==0:
        r.add(j)
        r.add(i//j)
      j+=1
    for j in r:
      c[j]+=1
      c[j]%=2
        
print(m)
print(*sorted(ans))
Buggy python submission (verdict: Time Limit Exceeded):
l,r=map(int,input().split())
m,ans=2019,2018
r=min(r,l+2019*2)
for i in range(l,r+1):
  for j in range(i+1,r+1):
    i%=m
    j%=m
    ans=min(ans,(i*j)%m)
print(ans)


Fixed submission:
l,r=map(int,input().split())
m=2019
if l//m<r//m:
  print(0)
else:
  ans=m
  for i in range(l%m, r%m+1):
    for j in range(i+1,r%m+1):
      ans=min(ans,i%m*j%m)
  print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
l,r=map(int,input().split())
m,ans=2019,2018
r=min(r,l+2019*2)
for i in range(l,r+1):
  for j in range(i+1,r+1):
    ans=min(ans,(i%m*j%m)%m)
print(ans)


Fixed submission:
l,r=map(int,input().split())
m=2019
if l//m<r//m:
  print(0)
else:
  ans=m
  for i in range(l%m, r%m+1):
    for j in range(i+1,r%m+1):
      ans=min(ans,i%m*j%m)
  print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
l,r=map(int,input().split())
m,ans=2019,2018
r=min(r,l+2019*2)
for i in range(l,r+1):
  for j in range(i+1,r+1):
    ans=min(ans,(i*j)%m)
print(ans)


Fixed submission:
l,r=map(int,input().split())
m=2019
if l//m<r//m:
  print(0)
else:
  ans=m
  for i in range(l%m, r%m+1):
    for j in range(i+1,r%m+1):
      ans=min(ans,i%m*j%m)
  print(ans)
Buggy python submission (verdict: Runtime Error):
def nCk(_n,_k):
  if _k==0:
    return 1
  else:
    if _n<0 or _k<0 or _n-_k<0:
      return 0
    else:
      return (fact[_n]//(fact[_k]*fact[_n-_k]))%m

fact=[1]*2005
for i in range(1,2001):
  fact[i]=fact[i-1]*i

n,k=map(int,input().split())
m=10**9+7
ans=cnt=0
for _k in range(1,k+1):
  ans=(nCk(n-k+_k,_k)-cnt)*nCk(k-1,_k-1) if _k>1 else n-k+_k 
  cnt+=ans
  cnt%=m
  ans%=m
  print(ans)


Fixed submission:
n=int(input())
a=list(map(int,input().split()))
ans=[0]*n
ans[0]=sum([2*a[i] for i in range(1,n,2)])
ans[0]=sum(a)-ans[0]

for i in range(n-1):
  ans[i+1]=2*a[i]-ans[i]

print(*ans)

Buggy python submission (verdict: Runtime Error):
l,r=map(int,input().split())
m,ans=2019,2018
r=min(r,l+2019*2)
for i in range(l,r+1):
  for j in range(i+1,r+1):
    i%=m
    j%=m
    ans=min(ans,(i*j)%m)
print(ans)


Fixed submission:
n=int(input())
a=list(map(int,input().split()))
ans=[0]*n
ans[0]=sum([2*a[i] for i in range(1,n,2)])
ans[0]=sum(a)-ans[0]

for i in range(n-1):
  ans[i+1]=2*a[i]-ans[i]

print(*ans)
Buggy python submission (verdict: Time Limit Exceeded):
T = int(input())

for _ in [0]*T:
    N = int(input())
    *A, = map(int,input().split())
    S = input()

    B = []
    ans = 0
    for s,a in zip(S[::-1],A[::-1]):
        if s=="0":
            B.append(a)
        else:
            # check
            C = B[:]
            for i in range(64):
                for b in C:
                    if (b >> i) & 1 == 1: break
                else:
                    continue
                if (a >> i) & 1 == 1: a ^= b
                for j,c in enumerate(C):
                    if (c >> i) & 1 == 1: C[j] ^= b
            if a!=0:
                ans = 1
                break
    print(ans)

Fixed submission:
T = int(input())

for _ in [0]*T:
    N = int(input())
    *A, = map(int,input().split())
    S = input()

    B = []
    ans = 0
    for s,a in zip(S[::-1],A[::-1]):
        if s=="0":
            B.append(a)
        else:
            # check
            C = B[:]
            for i in range(64):
                for b in C:
                    if (b >> i) & 1 == 1: break
                else:
                    continue
                if (a >> i) & 1 == 1: a ^= b
                for j,c in enumerate(C):
                    if (c >> i) & 1 == 1: C[j] ^= b
            if a!=0:
                ans = 1
                break
    print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
AB = [list(map(int,input().split())) for _ in [0]*N ]

mod = 1000000007

def gcd(x,y):
    if y==0:return x
    return gcd(y,x%y)

c = {}
n0 = 0
for a,b in AB:
    if a==b==0:
        n0 += 1
    elif a==0:
        c[(0,1)] = c.get((0,1),0) +1
    elif b==0:
        c[(1,0)] = c.get((1,0),0) +1
    else:
        g = gcd(a,b)
        a,b = a//g,b//g
        if a<0:
            a *= -1
            b *= -1
        c[(a,b)] = c.get((a,b),0) +1

ans = 1
done = set()
for k,n in c.items():
    if k in done: continue
    a,b = k
    if b>0:
        an,bn = b,-a
    else:
        an,bn = -b,a
    m = c.get((an,bn),0)
    ans *= (pow(2,n,mod) + pow(2,m,mod) - 1)%mod
    ans %= mod
    done.add((a,b))
    done.add((an,bn))

ans = ans -1 +n0
ans %= mod
print(ans)

Fixed submission:
N = int(input())
AB = [list(map(int,input().split())) for _ in [0]*N ]

mod = 1000000007

def gcd(x,y):
    if y==0:return x
    return gcd(y,x%y)

c = {}
n0 = 0
for a,b in AB:
    if a==b==0:
        n0 += 1
    elif a==0:
        c[(0,1)] = c.get((0,1),0) +1
    elif b==0:
        c[(1,0)] = c.get((1,0),0) +1
    else:
        g = gcd(a,b)
        a,b = a//g,b//g
        if a<0:
            a *= -1
            b *= -1
        c[(a,b)] = c.get((a,b),0) +1

ans = 1
done = set()
for k,n in c.items():
    if k in done: continue
    a,b = k
    if b>0:
        an,bn = b,-a
    else:
        an,bn = -b,a
    m = c.get((an,bn),0)
    ans *= (pow(2,n,mod) + pow(2,m,mod) - 1)%mod
    ans %= mod
    done.add((a,b))
    done.add((an,bn))

ans = ans -1 +n0
ans %= mod
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N,K = map(int,input().split())
*A, = map(int,input().split())

M = len(bin(K))-2

B = [[0]*N for _ in [0]*M]
B[0] = [a-1 for a in A]
for i in range(1,M):
    for j in range(N):
        B[i][j] = B[i-1][B[i-1][j]]

k = K
a = 0
while k>0:
    if k%2==1:
        a = B[0][a]
        k -= 1
        continue
    j = 1
    while k%(2**(j+1))==0:
        j += 1
    a = B[j][a]
    k -= 2**j
print(a+1)

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

M = len(bin(K))-2

B = [[0]*N for _ in [0]*M]
B[0] = [a-1 for a in A]
for i in range(1,M):
    for j in range(N):
        B[i][j] = B[i-1][B[i-1][j]]

k = K
a = 0
while k>0:
    if k%2==1:
        a = B[0][a]
        k -= 1
        continue
    j = 1
    while k%(2**(j+1))==0:
        j += 1
    a = B[j][a]
    k -= 2**j
print(a+1)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = [input() for _ in [0]*N]

A = [(0,0)]*N
B = [(0,0)]*N
for i,T in enumerate(S):
    m = 0
    M = 0
    tot = len(T) - T.count(")")*2
    if tot>=0:
        tot = 0
        for t in T:
            if t==")":
                tot -= 1
                m = min(m,tot)
            else:
                tot += 1
        A[i] = (m,tot)
    else:
        tot = 0
        for t in T[::-1]:
            if t==")":
                tot += 1
            else:
                tot -= 1
                m = min(m,tot)
        B[i] = (m,tot)

A.sort(reverse=True)
B.sort(reverse=True)

totA = 0
ans = True
for m,t in A:
    if totA + m < 0:
        ans = False
        break
    totA += t
totB = 0
for m,t in B:
    if totB + m < 0:
        ans = False
        break
    totB += t
if totA != totB:
    ans = False

if ans:
    print("Yes")
else:
    print("No")

Fixed submission:
N = int(input())
S = [input() for _ in [0]*N]

A = [(0,0)]*N
B = [(0,0)]*N
for i,T in enumerate(S):
    m = 0
    M = 0
    tot = len(T) - T.count(")")*2
    if tot>=0:
        tot = 0
        for t in T:
            if t==")":
                tot -= 1
                m = min(m,tot)
            else:
                tot += 1
        A[i] = (m,tot)
    else:
        tot = 0
        for t in T[::-1]:
            if t==")":
                tot += 1
            else:
                tot -= 1
                m = min(m,tot)
        B[i] = (m,tot)

A.sort(reverse=True)
B.sort(reverse=True)

totA = 0
ans = True
for m,t in A:
    if totA + m < 0:
        ans = False
        break
    totA += t
totB = 0
if ans:
    for m,t in B:
        if totB + m < 0:
            ans = False
            break
        totB += t
    if totA != totB:
        ans = False

if ans:
    print("Yes")
else:
    print("No")
Buggy python submission (verdict: Runtime Error):
N,A,B,C = map(int,input().split())
S = [input() for _ in [0]*N]

ans = [0]*N
for i,s in enumerate(S):
    if s=="AB":
        if A==B==0:
            print("No")
            break
        elif A==B==1:
            if s[(i+1)%N]=="BC":
                ans[i] = "B"
                B += 1
                A -= 1
            else:
                ans[i] = "A"
                A += 1
                B -= 1
        elif A>=B:
            ans[i] = "B"
            A -= 1
            B += 1
        else:
            ans[i] = "A"
            A += 1
            B -= 1
    elif s=="BC":
        if B==C==0:
            print("No")
            break
        elif B==C==1:
            if s[(i+1)%N]=="AC":
                ans[i] = "C"
                C += 1
                B -= 1
            else:
                ans[i] = "B"
                B += 1
                C -= 1
        elif B>=C:
            ans[i] = "C"
            B -= 1
            C += 1
        else:
            ans[i] = "B"
            B += 1
            C -= 1
    elif s=="AC":
        if A==C==0:
            print("No")
            break
        elif A==C==1:
            if s[(i+1)%N]=="BC":
                ans[i] = "C"
                C += 1
                A -= 1
            else:
                ans[i] = "A"
                A += 1
                C -= 1
        elif A>=C:
            ans[i] = "C"
            A -= 1
            C += 1
        else:
            ans[i] = "A"
            A += 1
            C -= 1
else:
    print("Yes")
    for out in ans:
        print(out)

Fixed submission:
N,A,B,C = map(int,input().split())
S = [input() for _ in [0]*N]

ans = [0]*N
for i,s in enumerate(S):
    if s=="AB":
        if A==B==0:
            print("No")
            break
        elif A==B==1:
            if S[(i+1)%N]=="BC":
                ans[i] = "B"
                B += 1
                A -= 1
            else:
                ans[i] = "A"
                A += 1
                B -= 1
        elif A>=B:
            ans[i] = "B"
            A -= 1
            B += 1
        else:
            ans[i] = "A"
            A += 1
            B -= 1
    elif s=="BC":
        if B==C==0:
            print("No")
            break
        elif B==C==1:
            if S[(i+1)%N]=="AC":
                ans[i] = "C"
                C += 1
                B -= 1
            else:
                ans[i] = "B"
                B += 1
                C -= 1
        elif B>=C:
            ans[i] = "C"
            B -= 1
            C += 1
        else:
            ans[i] = "B"
            B += 1
            C -= 1
    elif s=="AC":
        if A==C==0:
            print("No")
            break
        elif A==C==1:
            if S[(i+1)%N]=="BC":
                ans[i] = "C"
                C += 1
                A -= 1
            else:
                ans[i] = "A"
                A += 1
                C -= 1
        elif A>=C:
            ans[i] = "C"
            A -= 1
            C += 1
        else:
            ans[i] = "A"
            A += 1
            C -= 1
else:
    print("Yes")
    for out in ans:
        print(out)
Buggy python submission (verdict: Time Limit Exceeded):
S = input()
N = len(S)

dp = [[0]*2019 for _ in [0]*(N+1)]
ans = 0
for i,s in enumerate(S,1):
    s = int(s)
    dpi = dp[i]
    dpi1 = dp[i-1]
    dpi[s] += 1
    for j in range(2019):
        dpi[(j*10+s)%2019] += dpi1[j]
    ans += dpi[0]

print(ans)

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

dp = [[0]*2019 for _ in [0]*2]
ans = 0
for i,s in enumerate(S,1):
    s = int(s)
    i %= 2
    dpi = [0]*2019
    dpi1 = dp[1-i]
    dpi[s] += 1
    for j in range(2019):
        dpi[(j*10+s)%2019] += dpi1[j]
    dp[i] = dpi
    ans += dpi[0]

print(ans)

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

dp = [[0]*2019 for _ in [0]*(N+1)]
for i,s in enumerate(S,1):
    s = int(s)
    dpi = dp[i]
    dpi1 = dp[i-1]
    dpi[s] += 1
    for j in range(2019):
        dpi[(j*10+s)%2019] += dpi1[j]

ans = sum(dp[i][0] for i in range(N+1))
print(ans)

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

dp = [[0]*2019 for _ in [0]*2]
ans = 0
for i,s in enumerate(S,1):
    s = int(s)
    i %= 2
    dpi = [0]*2019
    dpi1 = dp[1-i]
    dpi[s] += 1
    for j in range(2019):
        dpi[(j*10+s)%2019] += dpi1[j]
    dp[i] = dpi
    ans += dpi[0]

print(ans)

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

dp = [[0]*2019 for _ in [0]*(N+1)]
for i,s in enumerate(S,1):
    s = int(s)
    dp[i][s] += 1
    for j in range(2019):
        dp[i][(j*10+s)%2019] += dp[i-1][j]

ans = sum(dp[i][0] for i in range(N+1))
print(ans)

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

dp = [[0]*2019 for _ in [0]*2]
ans = 0
for i,s in enumerate(S,1):
    s = int(s)
    i %= 2
    dpi = [0]*2019
    dpi1 = dp[1-i]
    dpi[s] += 1
    for j in range(2019):
        dpi[(j*10+s)%2019] += dpi1[j]
    dp[i] = dpi
    ans += dpi[0]

print(ans)