Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
s=input()
t=input()
score = 0
L = []
for i in range(len(s)-len(t)+1):
  cut = s[i:i+len(t)]
  for j in range(len(t)):
    if cut[j] == t[j] or cut[j] =="?":
      score += 1
  if score == len(t):
    s = s[:i] + t + s[i+len(t):]
    L.append(s.replace("?","a"))
  score = 0
if L = []:
  print("UNRESTORABLE")
else:
  L = sorted(L)
  print(L[0])
    


Fixed submission:
s=input()
t=input()
score = 0
L = []
for i in range(len(s)-len(t)+1):
  k = s
  cut = k[i:i+len(t)]
  for j in range(len(t)):
    if cut[j] == t[j] or cut[j] =="?":
      score += 1
  if score == len(t):
    
    k = k[:i] + t + k[i+len(t):]
    L.append(k.replace("?","a"))
  score = 0
if L == []:
  print("UNRESTORABLE")
else:
  L = sorted(L)
  print(L[0])
Buggy python submission (verdict: Runtime Error):
x,a,b=(int(i) for i in input().split())
c = b-c
if c <= 0:
  print('delicious')
elif c <= x:
  print('safe')
else:
  print('dangerous')

Fixed submission:
x,a,b=(int(i) for i in input().split())
c = b-a
if c <= 0:
  print('delicious')
elif c <= x:
  print('safe')
else:
  print('dangerous')

Buggy python submission (verdict: Runtime Error):
x,a,b=(int(i) for i in input().split())
c = b-c
if c <= 0:
  print('delicious')
elif c < x:
  print('safe')
else:
  print('dangerous')

Fixed submission:
x,a,b=(int(i) for i in input().split())
c = b-a
if c <= 0:
  print('delicious')
elif c <= x:
  print('safe')
else:
  print('dangerous')
Buggy python submission (verdict: Runtime Error):
n=int(input())
li=[int(i) for i in input().split()]
x = li[0]
ans = -1
count=0
for i in range(n):
  x = li[x-1]
  if x == 2:
    ans = count+1
    break
  count +=1
print(ans)

Fixed submission:
n=int(input())
li = []
for i in range(n):
  li += [int(input())]
x = li[0]
if x == 2:
    print(1)
    exit()
ans = -1
count=0
for i in range(n):
  x = li[x-1]
  count +=1
  if x == 2:
    print(count+1)
    exit()
print(-1)
Buggy python submission (verdict: Runtime Error):
n=int(input())
li = []
for i in range(n):
  li += [int(input())]
x = li[0]
ans = -1
count=0
for i in range(n):
  x = li[x-1]
  count +=1
  if x == 2:
    print(count+1)
    exit()
print(-1)

Fixed submission:
a,b = (int(i) for i in input().split())
if a+b >= 10:
  print('error')
else:
  print(a+b)
Buggy python submission (verdict: Runtime Error):
s = input()
ns = sorted(s)
ans = 'yes'
for i in range(len(s)):
  if s[i] == s[i+1]:
    ans = 'no'
print(ans)

Fixed submission:
s = input()
if len(s) == len(set(s)):
  print('yes')
else :
  print('no')

Buggy python submission (verdict: Runtime Error):
s = input()
ns = sorted(s)
ans = yes
for i in range(len(s)-1):
  if s[i] == s[i+1]:
    ans = no
print(ans)

Fixed submission:
s = input()
if len(s) == len(set(s)):
  print('yes')
else :
  print('no')
Buggy python submission (verdict: Runtime Error):
h,w = (int(i) for i in input().split())
a[]
for i in range(h):
  a.append(input())
print('#'*(w+2))
for i in range(h):
  print('#'+ a[i] + '#')
print('#'*(w+2))

Fixed submission:
h,w = (int(i) for i in input().split())
a=[ ]
for i in range(h):
  a.append(input())
print('#'*(w+2))
for i in range(h):
  print('#'+ a[i] + '#')
print('#'*(w+2))
Buggy python submission (verdict: Runtime Error):
h,w =map(int,input.split())

for i in range(h):
  s=input()
  print(s)
  print(s)

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

for i in range(h):
  s=input()
  print(s)
  print(s)
Buggy python submission (verdict: Runtime Error):
a = list(input())
b = list(input())
c = list(input())
key = "a"
for i in range(300):
  if key = "a":
    if len(a) == 0:
      print("A")
      break
    else:
      key = a[0]
      a = a[1:]
      
  elif key = "b":
    if len(b) == 0:
      print("B")
      break
    else:
      key = b[0]
      b = b[1:]
      
  else:
    if len(c) == 0:
      print("C")
      break
    else:
      key = c[0]
      c = c[1:]
    
      

Fixed submission:
a = list(input())
b = list(input())
c = list(input())
key = "a"
for i in range(300):
  if key == "a":
    if len(a) == 0:
      print("A")
      break
    else:
      key = a[0]
      a = a[1:]
      
  elif key == "b":
    if len(b) == 0:
      print("B")
      break
    else:
      key = b[0]
      b = b[1:]
      
  else:
    if len(c) == 0:
      print("C")
      break
    else:
      key = c[0]
      c = c[1:]
Buggy python submission (verdict: Runtime Error):
import sys
input=lambda: sys.stdin.readline().rstrip()
n=int(input())
X=input()
def popcount(x):
  x=x-((x>>1)&0x5555555555555555)
  x=(x&0x3333333333333333)+((x>>2)&0x3333333333333333)

  x=(x+(x>>4))&0x0f0f0f0f0f0f0f0f
  x=x+(x>>8)
  x=x+(x>>16)
  x=x+(x>>32)
  return x&0x0000007f

F=[0]*(n+1)
F[1]=1
F[2]=1
for i in range(3,n+1):
  F[i]=1+F[i%popcount(i)]

ct=X.count("1")
if ct==0:
  for _ in range(n):
    print(1)
else:
  a,b=0,0
  for i in range(n):
    if X[n-1-i]=="1":
      a=(a+pow(2,i,ct-1))%(ct-1)
      b=(b+pow(2,i,ct+1))%(ct+1)
  for i in range(n):
    if X[i]=="0":
      print(F[(b+pow(2,n-1-i,ct+1))%(ct+1)]+1)
    else:
      print(F[(a-pow(2,n-1-i,ct-1))%(ct-1)]+1)

Fixed submission:
import sys
input=lambda: sys.stdin.readline().rstrip()
n=int(input())
X=input()
def popcount(x):
  x=x-((x>>1)&0x5555555555555555)
  x=(x&0x3333333333333333)+((x>>2)&0x3333333333333333)

  x=(x+(x>>4))&0x0f0f0f0f0f0f0f0f
  x=x+(x>>8)
  x=x+(x>>16)
  x=x+(x>>32)
  return x&0x0000007f

F=[0]*(n+1)
F[1]=1
for i in range(2,n+1):
  F[i]=1+F[i%popcount(i)]

ct=X.count("1")
if ct==0:
  for _ in range(n):
    print(1)
elif ct==1:
  for i in range(n):
    if X[i]=="1":
      cur=i
      break
  for i in range(n):
    if i==cur:
      print(0)
    else:
      if i==n-1 or cur==n-1:
        print(2)
      else:
        print(1)

else:
  a,b=0,0
  for i in range(n):
    if X[n-1-i]=="1":
      a=(a+pow(2,i,ct-1))%(ct-1)
      b=(b+pow(2,i,ct+1))%(ct+1)
  for i in range(n):
    if X[i]=="0":
      print(F[(b+pow(2,n-1-i,ct+1))%(ct+1)]+1)
    else:
      print(F[(a-pow(2,n-1-i,ct-1))%(ct-1)]+1)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input=lambda: sys.stdin.readline().rstrip()
n=int(input())
A=[int(i) for i in input().split()]
tot=0
for a in A:
  tot^=a
T=[0]*30
for i in range(30):
  if tot&(1<<i):
    T[i]=1

Ans=[0]*n
for i in range(n):
  cur=0
  for j in range(30):
    if A[i]&(1<<j)>0 and T[j]==0:
      cur+=2**j
    elif A[i]&(1<<j)==0 and T[j]==1:
      cur+=2**j
  Ans[i]=cur
print(*Ans)
  

Fixed submission:
import sys
input=lambda: sys.stdin.readline().rstrip()
n=int(input())
A=[int(i) for i in input().split()]
tot=0
for a in A:
  tot^=a
T=[0]*30
for i in range(30):
  if tot&(1<<i):
    T[i]=1

Ans=[0]*n
for i in range(n):
  cur=0
  for j in range(30):
    if A[i]&(1<<j)>0 and T[j]==0:
      cur+=2**j
    elif A[i]&(1<<j)==0 and T[j]==1:
      cur+=2**j
  Ans[i]=cur
print(*Ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input=lambda: sys.stdin.readline().rstrip()
k=int(input())
S=input()
mod=10**9+7
n=len(S)
n_max=2*(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[n_max-1]=pow(F[n_max-1],mod-2,mod)
for i in reversed(range(n_max-1)):
  FI[i]=(FI[i+1]*(i+1))%mod
def comb(x,y):
  return (F[x]*FI[x-y]*FI[y])%mod

P1,P2=[1],[1]
for _ in range(10**6):
  P1.append((P1[-1]*26)%mod)
  P2.append((P2[-1]*25)%mod)

ans=0
for i in range(n,n+k+1):
  ans+=comb(i-1,n-1)*P2[i-n]*P1[n+k-i]
  ans%=mod
print(ans)


Fixed submission:
import sys
input=lambda: sys.stdin.readline().rstrip()
k=int(input())
S=input()
mod=10**9+7
n=len(S)
n_max=2*(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[n_max-1]=pow(F[n_max-1],mod-2,mod)
for i in reversed(range(n_max-1)):
  FI[i]=(FI[i+1]*(i+1))%mod
def comb(x,y):
  return (F[x]*FI[x-y]*FI[y])%mod

P1,P2=[1],[1]
for _ in range(10**6):
  P1.append((P1[-1]*26)%mod)
  P2.append((P2[-1]*25)%mod)

ans=0
for i in range(n,n+k+1):
  ans+=comb(i-1,n-1)*P2[i-n]*P1[n+k-i]
  ans%=mod
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input=lambda: sys.stdin.readline().rstrip()
S=input()
D=[0]*2019
cur=0
keta=0
ans=0
D[0]+=1
for s in S[::-1]:
  cur=(cur+int(s)*pow(10,keta))%2019
  ans+=D[cur]
  D[cur]+=1
  keta+=1
print(ans)

Fixed submission:
import sys
input=lambda: sys.stdin.readline().rstrip()
S=input()
n=len(S)
D=[0]*2019
T=[0]*(n+1)
T[0]=1
for i in range(n):
  T[i+1]=(T[i]*10)%2019

cur=0
keta=0
ans=0
D[0]+=1
for s in S[::-1]:
  cur=(cur+int(s)*T[keta])%2019
  ans+=D[cur]
  D[cur]+=1
  keta+=1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input=lambda: sys.stdin.readline().rstrip()
S=input()
import collections
D=collections.defaultdict(int)
cur=0
keta=0
ans=0
D[0]+=1
for s in S[::-1]:
  cur=(cur+int(s)*pow(10,keta))%2019
  ans+=D[cur]
  D[cur]+=1
  keta+=1
print(ans)

Fixed submission:
import sys
input=lambda: sys.stdin.readline().rstrip()
S=input()
n=len(S)
D=[0]*2019
T=[0]*(n+1)
T[0]=1
for i in range(n):
  T[i+1]=(T[i]*10)%2019

cur=0
keta=0
ans=0
D[0]+=1
for s in S[::-1]:
  cur=(cur+int(s)*T[keta])%2019
  ans+=D[cur]
  D[cur]+=1
  keta+=1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input=lambda: sys.stdin.readline().rstrip()
S=input()
import collections
D=collections.defaultdict(int)
cur=0
keta=0
ans=0
D[0]+=1
for s in S[::-1]:
  cur=(cur+int(s)*pow(10,keta))%2019
  ans+=D[cur]
  D[cur]+=1
  keta+=1
print(ans)

Fixed submission:
import sys
input=lambda: sys.stdin.readline().rstrip()
S=input()
n=len(S)
D=[0]*2019
T=[0]*(n+1)
T[0]=1
for i in range(n):
  T[i+1]=(T[i]*10)%2019

cur=0
keta=0
ans=0
D[0]+=1
for s in S[::-1]:
  cur=(cur+int(s)*T[keta])%2019
  ans+=D[cur]
  D[cur]+=1
  keta+=1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input=lambda: sys.stdin.readline().rstrip()
S=input()
import collections
D=collections.defaultdict(int)
cur=0
keta=0
ans=0
D[0]+=1
for s in S[::-1]:
  cur=(cur+int(s)*10**keta)%2019
  ans+=D[cur]
  D[cur]+=1
  keta+=1
print(ans)

Fixed submission:
import sys
input=lambda: sys.stdin.readline().rstrip()
S=input()
n=len(S)
D=[0]*2019
T=[0]*(n+1)
T[0]=1
for i in range(n):
  T[i+1]=(T[i]*10)%2019

cur=0
keta=0
ans=0
D[0]+=1
for s in S[::-1]:
  cur=(cur+int(s)*T[keta])%2019
  ans+=D[cur]
  D[cur]+=1
  keta+=1
print(ans)
Buggy python submission (verdict: Runtime Error):
import sys
input=lambda: sys.stdin.readline().rstrip()
import heapq
n,m,s=map(int,input().split())
E=[]
for _ in range(m):
  E.append(tuple(map(int,input().split())))
CD=[]
for _ in range(n):
  CD.append(tuple(map(int,input().split())))
nn=n*2500
edge=[[] for i in range(nn)]
for u,v,a,b in E:
  u-=1
  v-=1
  for i in range(a,2500):
    edge[u*2500+i].append(b*10**6+v*2500+i-a)
    edge[v*2500+i].append(b*10**6+u*2500+i-a)
for i in range(n):
  c,d=CD[i]
  for j in range(2500):
    if j+c<2500:
      edge[i*2500+j].append(d*10**6+i*2500+j+c)

def dijkstra_heap(s):
  d=[float("inf")]*nn
  used=[True]*nn
  d[s]=0
  used[s]=False
  edgelist=[]
  for e in edge[s]:
    heapq.heappush(edgelist,e)
  while edgelist:
    minedge=heapq.heappop(edgelist)
    minedge_cost=minedge//(10**6)
    minedge_v=minedge%(10**6)
    if not used[minedge_v]:
      continue
    d[minedge_v] = minedge_cost
    used[minedge_v] = False
    for e in edge[minedge_v]:
      e_cost=e//(10**6)
      e_v=e%(10**6)
      if used[e_v]:
        heapq.heappush(edgelist,e+minedge_cost*10**6)
  return d
D=dijkstra_heap(s)
for i in range(1,n):
  ans=D[i*2500]
  for j in range(1,2500):
    ans=min(ans,D[i*2500+j])
  print(ans)


Fixed submission:
import sys
input=lambda: sys.stdin.readline().rstrip()
import heapq
n,m,s=map(int,input().split())
s=min(s,2499)
E=[]
for _ in range(m):
  E.append(tuple(map(int,input().split())))
CD=[]
for _ in range(n):
  CD.append(tuple(map(int,input().split())))
nn=n*2500
edge=[[] for i in range(nn)]
for u,v,a,b in E:
  u-=1
  v-=1
  for i in range(a,2500):
    edge[u*2500+i].append(b*10**6+v*2500+i-a)
    edge[v*2500+i].append(b*10**6+u*2500+i-a)
for i in range(n):
  c,d=CD[i]
  for j in range(2500):
    if j+c<2500:
      edge[i*2500+j].append(d*10**6+i*2500+j+c)

def dijkstra_heap(s):
  d=[float("inf")]*nn
  used=[True]*nn
  d[s]=0
  used[s]=False
  edgelist=[]
  for e in edge[s]:
    heapq.heappush(edgelist,e)
  while edgelist:
    minedge=heapq.heappop(edgelist)
    minedge_cost=minedge//(10**6)
    minedge_v=minedge%(10**6)
    if not used[minedge_v]:
      continue
    d[minedge_v] = minedge_cost
    used[minedge_v] = False
    for e in edge[minedge_v]:
      e_cost=e//(10**6)
      e_v=e%(10**6)
      if used[e_v]:
        heapq.heappush(edgelist,e+minedge_cost*10**6)
  return d
D=dijkstra_heap(s)
for i in range(1,n):
  ans=D[i*2500]
  for j in range(1,2500):
    ans=min(ans,D[i*2500+j])
  print(ans)
Buggy python submission (verdict: Runtime Error):
import sys
input=lambda: sys.stdin.readline().rstrip()
h,w=map(int,input().split())
ans=((h+1)//2+h//2)*(w//2)
if w%2==1:
  ans+=(h+1)//2
if h==1 or w==1:
  ans=1
peint(ans)

Fixed submission:
import sys
input=lambda: sys.stdin.readline().rstrip()
h,w=map(int,input().split())
ans=((h+1)//2+h//2)*(w//2)
if w%2==1:
  ans+=(h+1)//2
if h==1 or w==1:
  ans=1
print(ans)
Buggy python submission (verdict: Runtime Error):
import sys
input=lambda: sys.stdin.readline().rstrip()
n=int(input())

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

inf=float("inf")

prv=[inf]*n
prv[0]=-1
depth=[inf]*n
depth[0]=0
stack=[0]
while stack:
  cur=stack.pop()
  for next in edge[cur]:
    if prv[next]==inf:
      prv[next]=cur
      depth[next]=depth[cur]+1
      stack.append(next)
Ans=[0]*n
Ans[0]=1
ct1,ct2,ct3=1,0,0
for i in range(1,n):
  if depth(i)%2==0:
    if 3*ct1+1<=n:
      Ans[i]=3*ct1+1
      ct1+=1
    else:
      Ans[i]=3*ct3+3
      ct3+=1
  else:
    if 3*ct2+2<=n:
      Ans[i]=3*ct2+2
      ct2+=1
    else:
      Ans[i]=3*ct3+3
      ct3+=1
if max(Ans)>n:
  print(-1)
else:
  print(*Ans)



Fixed submission:
import sys
input=lambda: sys.stdin.readline().rstrip()
n=int(input())

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

inf=float("inf")

prv=[inf]*n
prv[0]=-1
depth=[inf]*n
depth[0]=0
stack=[0]
while stack:
  cur=stack.pop()
  for next in edge[cur]:
    if prv[next]==inf:
      prv[next]=cur
      depth[next]=depth[cur]+1
      stack.append(next)
e,o=0,0
for i in range(n):
  if depth[i]%2:
    o+=1
  else:
    e+=1
Ans=[0]*n
if e<=n//3:
  ct1,ct2,ct3=0,0,0
  for i in range(n):
    if not depth[i]%2:
      Ans[i]=3*ct3+3
      ct3+=1
    else:
      if 3*ct2+2<=n:
        Ans[i]=3*ct2+2
        ct2+=1
      elif 3*ct1+1<=n:
        Ans[i]=3*ct1+1
        ct1+=1
      else:
        Ans[i]=3*ct3+3
        ct3+=1
elif o<=n//3:
  ct1,ct2,ct3=0,0,0
  for i in range(n):
    if depth[i]%2:
      Ans[i]=3*ct3+3
      ct3+=1
    else:
      if 3*ct1+1<=n:
        Ans[i]=3*ct1+1
        ct1+=1
      elif 3*ct2+2<=n:
        Ans[i]=3*ct2+2
        ct2+=1
      else:
        Ans[i]=3*ct3+3
        ct3+=1
else:
  ct1,ct2,ct3=0,0,0
  for i in range(n):
    if not depth[i]%2:
      if 3*ct1+1<=n:
        Ans[i]=3*ct1+1
        ct1+=1
      else:
        Ans[i]=3*ct3+3
        ct3+=1
    else:
      if 3*ct2+2<=n:
        Ans[i]=3*ct2+2
        ct2+=1
      else:
        Ans[i]=3*ct3+3
        ct3+=1

print(*Ans)
Buggy python submission (verdict: Time Limit Exceeded):
s=input()
q=int(input())
sign=1
for i in range(q):
  Q=[str(i) for i in input().split()]
  if Q[0]=="1":
    sign*=-1
  else:
    f,c=Q[1:]
    if f=="1" and sign==1:
      s=c+s
    elif f=="2" and sign==-1:
      s=c+s
    else:
      s=s+c
print(s if sign==1 else s[::-1])

Fixed submission:
import sys
input = lambda: sys.stdin.readline().rstrip()
s=input()
q=int(input())
sign=1
F,B="",""
for i in range(q):
  Q=[str(i) for i in input().split()]
  if Q[0]=="1":
    sign*=-1
  else:
    f,c=Q[1:]
    if f=="1" and sign==1:
      F=c+F
    elif f=="2" and sign==-1:
      F=c+F
    else:
      B=B+c
ans=F+s+B
print(ans if sign==1 else ans[::-1])

Buggy python submission (verdict: Time Limit Exceeded):
s=input()
q=int(input())
sign=1
for i in range(q):
  Q=[str(i) for i in input().split()]
  if Q[0]=="1":
    sign*=-1
  else:
    f,c=Q[1:]
    if f=="1" and sign==1:
      s=c+s
    elif f=="2" and sign==-1:
      s=c+s
    else:
      s=s+c
print(s if sign==1 else s[::-1])

Fixed submission:
import sys
input = lambda: sys.stdin.readline().rstrip()
s=input()
q=int(input())
sign=1
F,B="",""
for i in range(q):
  Q=[str(i) for i in input().split()]
  if Q[0]=="1":
    sign*=-1
  else:
    f,c=Q[1:]
    if f=="1" and sign==1:
      F=c+F
    elif f=="2" and sign==-1:
      F=c+F
    else:
      B=B+c
ans=F+s+B
print(ans if sign==1 else ans[::-1])
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
S=input()
q=int(input())

D=[[0]*26 for _ in range(n+1)]
for i,s in enumerate(S):
  for j in range(26):
    if j==ord(s)-97:
      D[i+1][j]=D[i][j]+1
    else:
      D[i+1][j]=D[i][j]

n_max=5*10**5
nn=n_max.bit_length()+1
BITS=[[0]*(2**nn) for _ in range(26)]
for i in range(26):
  BITS[i].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

for _ in range(q):
  q1,q2,q3=map(str,input().split())
  if q1=="1":
    num=int(q2)-1
    prev=ord(S[num])-97
    new=ord(q3)-97
    bitadd(BITS[prev],num,-1)
    bitadd(BITS[new],num,1)
  else:
    l,r=int(q2),int(q3)
    ans=0
    for i in range(26):
      diff=D[r][i]-D[l-1][i]+bitsum(BITS[i],r)-bitsum(BITS[i],l-1)
      if diff:
        ans+=1
    print(ans)



Fixed submission:
n=int(input())
S=list(input())
q=int(input())

D=[[0]*26 for _ in range(n+1)]
for i,s in enumerate(S):
  for j in range(26):
    if j==ord(s)-97:
      D[i+1][j]=D[i][j]+1
    else:
      D[i+1][j]=D[i][j]

n_max=n+1
nn=n_max.bit_length()+1
BITS=[[0]*(2**nn) for _ in range(26)]
for i in range(26):
  BITS[i].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

for _ in range(q):
  q1,q2,q3=map(str,input().split())
  if q1=="1":
    num=int(q2)-1
    prev=ord(S[num])-97
    new=ord(q3)-97
    S[num]=q3
    if prev!=new:
      bitadd(BITS[prev],num+1,-1)
      bitadd(BITS[new],num+1,1)
  else:
    l,r=int(q2),int(q3)
    ans=0
    for i in range(26):
      diff=D[r][i]-D[l-1][i]+bitsum(BITS[i],r)-bitsum(BITS[i],l-1)
      if diff>0:
        ans+=1
    print(ans)
Buggy python submission (verdict: Runtime Error):
n=int(input())
A=[int(i) for i in input().split()]
if len(set(A))==n:
    print("YES")
else:
    print("NO")

Fixed submission:
n,k=map(int,input().split())
P=[int(i) for i in input().split()]
ans=0
for i in range(k):
  ans+=(P[i]+1)/2
cur=ans
for i in range(k,n):
  cur+=(P[i]+1)/2
  cur-=(P[i-k]+1)/2
  if cur>ans:
    ans=cur
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
r1,c1,r2,c2=map(int,input().split())
mod=10**9+7
n_max=2*(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

def f(x,y):
  return comb(x+y+2,y+1)-1

print((f(r2,c2)-f(r2,c1-1)-f(r1-1,c2)+f(r1-1,c1-1))%mod)


Fixed submission:
r1,c1,r2,c2=map(int,input().split())
mod=10**9+7
n_max=2*(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

def f(x,y):
  return comb(x+y+2,y+1)-1

print((f(r2,c2)-f(r2,c1-1)-f(r1-1,c2)+f(r1-1,c1-1))%mod)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input=sys.stdin.readline
n=int(input())
Edge=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  Edge[a-1].append((b-1,i))
  Edge[b-1].append((a-1,i))
m=int(input())
M=[]
for i in range(m):
  M.append(tuple(map(int,input().split())))

inf=float("inf")
path=[-1]*n #根から各点までのパスが通過する辺をbitで管理したもの
path[0]=0
stack=[0]
while stack:
  cur=stack.pop()
  for next,num in Edge[cur]:
    if path[next]==-1:
      path[next]=path[cur]|(1<<num)
      stack.append(next)

def popcount(x):
  return bin(x).count("1")

passing=[] #Mの各u,vについて、通過する辺をbitで持ったもの
for u,v in M:
  passing.append((path[u-1]^path[v-1]))

ans=2**(n-1)
#Mのすべての部分集合について符号付で足し合わせる
for i in range(1,2**m):
  i_ct=popcount(i)#満たすべき条件の数、これで符号を決める
  condition=0
  for j in range(m):
    if i&(1<<j):#j番目の条件を満たす
      condition=condition|passing[j]
  cond_ct=popcount(condition) #iが表すMの部分集合の条件をすべて満たす場合にすべて白になる辺集合の要素数

  ans+=((-1)**i_ct)*(2**(n-1-cond_ct))
print(ans)

Fixed submission:
import sys
input=sys.stdin.readline
n=int(input())
Edge=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  Edge[a-1].append((b-1,i))
  Edge[b-1].append((a-1,i))
m=int(input())
M=[]
for i in range(m):
  M.append(tuple(map(int,input().split())))

inf=float("inf")
path=[-1]*n #根から各点までのパスが通過する辺をbitで管理したもの
path[0]=0
stack=[0]
while stack:
  cur=stack.pop()
  for next,num in Edge[cur]:
    if path[next]==-1:
      path[next]=path[cur]|(1<<num)
      stack.append(next)

def popcount(x):
  return bin(x).count("1")

passing=[] #Mの各u,vについて、通過する辺をbitで持ったもの
for u,v in M:
  passing.append((path[u-1]^path[v-1]))

ans=2**(n-1)
#Mのすべての部分集合について符号付で足し合わせる
for i in range(1,2**m):
  i_ct=popcount(i)#満たすべき条件の数、これで符号を決める
  condition=0
  for j in range(m):
    if i&(1<<j):#j番目の条件を満たす
      condition=condition|passing[j]
  cond_ct=popcount(condition) #iが表すMの部分集合の条件をすべて満たす場合にすべて白になる辺集合の要素数

  ans+=pow((-1),i_ct)*pow(2,n-1-cond_ct)
print(ans)
Buggy python submission (verdict: Runtime Error):
n=int(input())
X=[int(i) for i in input().split()]
mod=10**9+7
n_max=n
F=[0]*(n_max+1)
F[0]=1
for i in range(n_max):
  F[i+1]=(F[i]*(i+1))%mod

ans=0
DP=[[0]*n for _ in range(n)]
for i in range(1,n):
  for j in range(1,i+1):
    if j==1:
      DP[i][j]=F[i-1]
    elif j==i:
      DP[i][j]=1
    else:
      DP[i][j]=DP[i-1][j-1]+(i-1)*DP[i-1][j]
    ans=(ans+j*DP[i][j]*(X[i]-X[i-1])*F[n-1]//F[i])%mod
print(ans)

Fixed submission:
import sys
n=int(input())
X=[int(i) for i in input().split()]
mod=10**9+7
n_max=n
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)


ans=0
DP=[0]*n
DP[0]=1
DP[1]=1
ans=(ans+DP[1]*(X[1]-X[0])*F[n-1]*FI[0])%mod
for i in range(2,n):
  DP[i]=(F[i-1]+DP[i-1]*i)%mod
  ans=(ans+DP[i]*(X[i]-X[i-1])*F[n-1]*FI[i])%mod
print(ans)

Buggy python submission (verdict: Runtime Error):
n=int(input())
X=[int(i) for i in input().split()]
mod=10**9+7
n_max=2*10**5
F=[0]*(n_max+1)
F[0]=1
for i in range(n_max):
  F[i+1]=(F[i]*(i+1))%mod

ans=0
DP=[[0]*n for _ in range(n)]
for i in range(1,n):
  for j in range(1,i+1):
    if j==1:
      DP[i][j]=F[i-1]
    elif j==i:
      DP[i][j]=1
    else:
      DP[i][j]=DP[i-1][j-1]+(i-1)*DP[i-1][j]
  for j in range(1,i+1):
    ans=(ans+j*DP[i][j]*(X[i]-X[i-1])*F[n-i])%mod
print(ans)

Fixed submission:
import sys
n=int(input())
X=[int(i) for i in input().split()]
mod=10**9+7
n_max=n
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)


ans=0
DP=[0]*n
DP[0]=1
DP[1]=1
ans=(ans+DP[1]*(X[1]-X[0])*F[n-1]*FI[0])%mod
for i in range(2,n):
  DP[i]=(F[i-1]+DP[i-1]*i)%mod
  ans=(ans+DP[i]*(X[i]-X[i-1])*F[n-1]*FI[i])%mod
print(ans)