Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
h,w,K=map(int,input().split())
s=[]
for i in range(h):
    s.append(input())

ans=float("inf")
for i in range(2**(h-1)):
    cut=[]
    linecount=0
    for j in range(h-1):
        if (i>>j)%2==1:
            cut.append(j)
    counter=[0]*(len(cut)+1)
    for j in range(w):
        ncounter=[0]*(len(cut)+1)
        area=0
        flag=False
        for k in range(h):
            ncounter[area]+=(s[k][j]=="1")
            if counter[area]+ncounter[area]>K:
                flag=True
            if k in cut:
                area+=1
        if flag:
            counter=ncounter[:]
            linecount+=1
        else:
            for l in range(len(cut)+1):
                counter[l]+=ncounter[l]
    ans=min(ans,linecount+len(cut))
print(ans)
        





Fixed submission:
h,w,K=map(int,input().split())
s=[]
for i in range(h):
    s.append(input())

ans=float("inf")
for i in range(2**(h-1)):
    cut=[]
    linecount=0
    for j in range(h-1):
        if (i>>j)%2==1:
            cut.append(j)
    counter=[0]*(len(cut)+1)
    for j in range(w):
        ncounter=[0]*(len(cut)+1)
        area=0
        flag=False
        for k in range(h):
            ncounter[area]+=int(s[k][j])
            if counter[area]+ncounter[area]>K:
                if ncounter[area]>K:
                    linecount=float("inf")
                flag=True
            if k in cut:
                area+=1
        if flag:
            counter=ncounter[:]
            linecount+=1
        else:
            for l in range(len(cut)+1):
                counter[l]+=ncounter[l]
    ans=min(ans,linecount+len(cut))
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
H,W=map(int,input().split())
S=[input() for _ in range(H)]
ans=float("inf")
def search(i,j,count):
    global ans
    if i==H-1 and j==W-1:
        ans=min(ans,count)
        
    counti=count
    countj=count

    if j<W-1:
        if S[i][j]=="." and S[i][j+1]=="#":
            countj+=1
        search(i,j+1,countj)
    if i<H-1:
        if S[i][j]=="." and S[i+1][j]=="#":
            counti+=1
        search(i+1,j,counti)
search(0,0,1*(S[0][0]=="#"))
print(ans)

Fixed submission:
H,W=map(int,input().split())
S=[input() for _ in range(H)]
ans=float("inf")

counter=[[999]*W for _ in range(H)]

def search(i,j,count):
    global ans

    if counter[i][j]!=999:
        ans=min(ans,count+counter[i][j])
        return(counter[i][j])

    dist=999

    if i==H-1 and j==W-1:
        ans=min(ans,count)
        return 0
    countj=count
    counti=count
    
    if j<W-1:
        if S[i][j]=="." and S[i][j+1]=="#":
            countj+=1
        dist=search(i,j+1,countj) + (S[i][j]=="." and S[i][j+1]=="#")
    if i<H-1:
        if S[i][j]=="." and S[i+1][j]=="#":
            counti+=1
        dist=min(dist,search(i+1,j,counti)+(S[i][j]=="." and S[i+1][j]=="#"))
    
    counter[i][j]=dist
    return dist
search(0,0,(S[0][0]=="#")*1)
print(ans)
Buggy python submission (verdict: Runtime Error):
import collections
n=input()
s=[]
for i in range(n):
    s.append(input())
c=collections.Counter(s).most_common()


print(c[0][0])
mx=c[0][1]
for i in range(1,len(c)):
    if c[i][1]==mx:
        print(c[i][0])
    else:
        exit()
    

Fixed submission:
n = int(input())

s_list = [""]*n

for i in range(n):
    s_list[i] = input()

s_list.sort()

ans_list = [s_list[0]]
pre_s = s_list[0]
count = 1
max_count = count

if len(s_list) == len(set(s_list)):
    ans_list = s_list
        
    ans_list.sort()

    for s in ans_list:
        print(s)

    exit()


for i in range(1,n):
    if pre_s == s_list[i]:
        count += 1
        if count == max_count:
            ans_list.append(s_list[i])
        if count > max_count:
            max_count = count
            ans_list = [s_list[i]]
    else:
        pre_s = s_list[i]
        count = 1

ans_list.sort()

for s in ans_list:
    print(s)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())

dic = {}

for i in range(n):
    s = input()
    if s in dic:
        dic[s] += 1
    else:
        dic[s] = 1

max_k_list = [kv[0] for kv in dic.items() if kv[1] == max(dic.values())]
max_k_list.sort()

for s in max_k_list:
    print(s)


Fixed submission:
n = int(input())

s_list = [""]*n

for i in range(n):
    s_list[i] = input()

s_list.sort()

ans_list = [s_list[0]]
pre_s = s_list[0]
count = 1
max_count = count

if len(s_list) == len(set(s_list)):
    ans_list = s_list
        
    ans_list.sort()

    for s in ans_list:
        print(s)

    exit()


for i in range(1,n):
    if pre_s == s_list[i]:
        count += 1
        if count == max_count:
            ans_list.append(s_list[i])
        if count > max_count:
            max_count = count
            ans_list = [s_list[i]]
    else:
        pre_s = s_list[i]
        count = 1

ans_list.sort()

for s in ans_list:
    print(s)
Buggy python submission (verdict: Time Limit Exceeded):
s = input()[::-1]
s += "0"
n = len(s)

dp = [[1001001001]*2 for _ in range(n+1)]

dp[0][0] = 0

for i in range(n):
    for j in range(2):
        x = int(s[i]) + j

        if x < 10:
            dp[i+1][0] = min(dp[i][j] + x,dp[i+1][0])
        if x > 0:
            dp[i+1][1] = min(dp[i][j] + (10 - x),dp[i+1][1])


print(dp[n][0])

Fixed submission:
s = input()[::-1]
s += "0"
n = len(s)

dp = [[1001001001]*2 for _ in range(n+1)]

dp[0][0] = 0

for i in range(n):
    for j in range(2):
        x = int(s[i]) + j

        if x < 10:
            dp[i+1][0] = min(dp[i][j] + x,dp[i+1][0])
        if x > 0:
            dp[i+1][1] = min(dp[i][j] + (10 - x),dp[i+1][1])


print(dp[n][0])

Buggy python submission (verdict: Time Limit Exceeded):
s = input()[::-1]
s += "0"
n = len(s)

dp = [[1001001001]*2 for _ in range(n+1)]

dp[0][0] = 0

for i in range(n):
    for j in range(2):
        x = int(s[i]) + j
        for a in range(10):
            ni = i + 1
            nj = 0
            b = a - x
            if b < 0:
                nj = 1
                b += 10
            dp[ni][nj] = min(dp[ni][nj], dp[i][j] + a + b)

print(dp[n][0])

Fixed submission:
s = input()[::-1]
s += "0"
n = len(s)

dp = [[1001001001]*2 for _ in range(n+1)]

dp[0][0] = 0

for i in range(n):
    for j in range(2):
        x = int(s[i]) + j

        if x < 10:
            dp[i+1][0] = min(dp[i][j] + x,dp[i+1][0])
        if x > 0:
            dp[i+1][1] = min(dp[i][j] + (10 - x),dp[i+1][1])


print(dp[n][0])
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A_List = list(map(int,input().split()))

for i in range(N):
    for j in range(i+1,N):
        if A_List[i]==A_List[j]:
            print("NO")
            exit()

print("YES")

Fixed submission:
N = int(input())
A_List = list(map(int,input().split()))

print("YES" if len(A_List)==len(set(A_List)) else "NO")
Buggy python submission (verdict: Time Limit Exceeded):
H,N=map(int,input().split())
AB=[]
for i in range(N):
    AB.append(list(map(int,input().split())))
maxA=max(AB)[0]
#dp[i] ひとつ前までの呪文で体力iを削るために必要な最小魔法消費量
dp=[float("inf")]*(H+maxA)
ndp=[float("inf")]*(H+maxA)
dp[0]=0
for j in range(N):
    for i in range(H+1):
        ndp[i]=dp[i]
    cost=AB[j][1]
    fire=AB[j][0]
    for i in range(H+1):
        repeat=0
        while i+fire*repeat<H:
            repeat+=1
            ndp[i+fire*repeat]=min(dp[i]+cost*repeat,ndp[i+fire*repeat])
    dp=ndp[:]

ans=float("inf")
for i in range(H,H+maxA):
    ans=min(ans,dp[i])
print(ans)







Fixed submission:
H,N=map(int,input().split())
AB=[]
for i in range(N):
    AB.append(list(map(int,input().split())))
maxA=max(AB)[0]
#dp[i] 敵に合計iダメージを与えるのに必要な最小魔力量
dp=[float("inf")]*(H+maxA)
dp[0]=0
for i in range(H):
    for fire,cost in AB:
        dp[i+fire]=min(dp[i+fire],dp[i]+cost)

ans=min(dp[H:])
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
H,N=map(int,input().split())
AB=[]
for i in range(N):
    AB.append(list(map(int,input().split())))
maxA=max(AB)[0]
#dp[i] ひとつ前までの呪文で体力iを削るために必要な最小魔法消費量
dp=[float("inf")]*(H+maxA)
ndp=[float("inf")]*(H+maxA)
dp[0]=0
for j in range(N):
    for i in range(H+1):
        ndp[i]=dp[i]
    cost=AB[j][1]
    fire=AB[j][0]
    for i in range(H+1):
        repeat=0
        while i+fire*repeat<H:
            repeat+=1
            ndp[i+fire*repeat]=min(dp[i]+cost*repeat,ndp[i+fire*repeat])
    dp=ndp[:]

ans=float("inf")
for i in range(H,H+maxA):
    ans=min(ans,dp[i])
print(ans)







Fixed submission:
H,N=map(int,input().split())
AB=[]
for i in range(N):
    AB.append(list(map(int,input().split())))
maxA=max(AB)[0]
#dp[i] 敵に合計iダメージを与えるのに必要な最小魔力量
dp=[float("inf")]*(H+maxA)
dp[0]=0
for i in range(H):
    for fire,cost in AB:
        dp[i+fire]=min(dp[i+fire],dp[i]+cost)

ans=min(dp[H:])
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
H,N=map(int,input().split())
AB=[]
for i in range(N):
    AB.append(list(map(int,input().split())))
maxh=10**4
#dp[i] ひとつ前までの呪文で体力iを削るために必要な最小魔法消費量
dp=[float("inf")]*(2*maxh+1)
ndp=[float("inf")]*(2*maxh+1)
dp[0]=0
for j in range(N):
    for i in range(H+1):
        ndp[i]=dp[i]
    cost=AB[j][1]
    fire=AB[j][0]
    for i in range(H+1):
        repeat=0
        while i+fire*repeat<H:
            repeat+=1
            ndp[i+fire*repeat]=min(dp[i]+cost*repeat,ndp[i+fire*repeat])
    dp=ndp[:]

ans=float("inf")
for i in range(H,2*maxh+1):
    ans=min(ans,dp[i])
print(ans)







Fixed submission:
H,N=map(int,input().split())
AB=[]
for i in range(N):
    AB.append(list(map(int,input().split())))
maxA=max(AB)[0]
#dp[i] 敵に合計iダメージを与えるのに必要な最小魔力量
dp=[float("inf")]*(H+maxA)
dp[0]=0
for i in range(H):
    for fire,cost in AB:
        dp[i+fire]=min(dp[i+fire],dp[i]+cost)

ans=min(dp[H:])
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())

count=0
for i in range(1,N+1):
    head=int(str(i)[0])
    hip=i%10
    jstart=head-hip
    if jstart<0:
        jstart+=10
    for j in range(jstart,N+1-i,10):
        if str(i+j)[0]==str(i)[-1]:
            count+=2
            if j==0:
                count-=1
            else:
            	pass
        else:
            j=(int(str(i+j)[0])+1)*10**(len(str(i+j))-1)+jstart

print(count)


Fixed submission:
N = int(input())

c = [[0]*10 for _ in range(10)]

for k in range(1,N+1):
    c[int(str(k)[0])][int(str(k)[-1])]+=1

ans = 0

for k in range(81):
    i = k // 9 + 1
    j = k % 9 + 1
    ans += c[i][j] * c[j][i]

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect_left as BL 
N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort()

#border以上の幸福度を返す握手の組の数が、M以上であるか
def isok(border):
  res=0
  for i in range(N):
    res+=N-BL(A,border-A[i])
  return res>=M
    

ok=0
ng=A[-1]*2+1
mid=(ok+ng)//2

#幸福度h以上の握手がM組以上存在するような最大のhを探す
while abs(ok-ng)>1:
  mid=(ok+ng)//2
  if isok(mid):
    ok=mid
  else:
    ng=mid
  
ans=0
shake_c=0
for i in range(N):
  goodshake=N-BL(A,ok-A[i])
  shake_c+=goodshake
  for j in range(goodshake):
    ans+=A[i]+A[-1-j]
    
ans-=(shake_c-M)*ok
print(ans)
  

Fixed submission:
from bisect import bisect_left as BL 
N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort()

#border以上の幸福度を返す握手の組の数が、M以上であるか
def isok(border):
  res=0
  for i in range(N):
    res+=N-BL(A,border-A[i])
  return res>=M
    

ok=0
ng=A[-1]*2+1
mid=(ok+ng)//2

#幸福度h以上の握手がM組以上存在するような最大のhを探す
while abs(ok-ng)>1:
  mid=(ok+ng)//2
  if isok(mid):
    ok=mid
  else:
    ng=mid
  
B=reversed(A)
SB=[0]
for b in B:
  SB.append(b+SB[-1])
  
ans=0
shake_c=0
for i in range(N):
  goodshake=N-BL(A,ok-A[i])
  shake_c+=goodshake
  ans+=A[i]*goodshake
  ans+=SB[goodshake]  
ans-=(shake_c-M)*ok
print(ans)
Buggy python submission (verdict: Runtime Error):
N=int(input())
AB=[list(map(int,input().split())) for _ in range(N)]

dist=[[0]*N in range(N)]
for i in range(N):
  for j in range(N):
    dist[i][j]=((AB[i][0]-AB[j][0])**2+(AB[i][1]-AB[j][1])**2)**0.5
    
ans=0
def go(town,rest):
  for i in len(rest):
    nrest=rest[:]
    ntown=nrest.pop(i)
    ans+=dist[town][ntown]
    if len(rest)==0:
      return
    go(ntown,nrest)
    
print(ans)


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

dist=[[0]*N for _ in range(N)]
ans=0
for i in range(N):
  for j in range(N):
    if i==j:
      continue
    ans+=((AB[i][0]-AB[j][0])**2+(AB[i][1]-AB[j][1])**2)**0.5
ans/=N
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N,T=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(N)]
#dp[i][j] 料理iまでの間で、時間jまでに達成できる最大効用
dp=[[0]*(T+1) for _ in range(N+1)]
AB.sort()
for i in range(1,N+1):
  dp[i]=dp[i-1][:]
  time=AB[i-1][0]
  happy=AB[i-1][1]
  for j in range(T):
    dp[i][min(j+time,T)]=max(dp[i][min(j+time,T)],dp[i-1][j]+happy)
print(dp[N][T])
    

Fixed submission:
N,T=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(N)]
#dp[i][j] 料理iまでの間で、時間jまでに達成できる最大効用
dp=[[0]*(T+1) for _ in range(N+1)]
AB.sort()
for i in range(1,N+1):
  dp[i]=dp[i-1][:]
  time=AB[i-1][0]
  happy=AB[i-1][1]
  for j in range(T):
    dp[i][min(j+time,T)]=max(dp[i][min(j+time,T)],dp[i-1][j]+happy)
print(dp[N][T])
Buggy python submission (verdict: Runtime Error):
N=int(input())
can=[]
for i in range(1,N**0.5+1):
  if N%i==0:
    can.append(N-1+N//i-1)
    

print(min(can))

Fixed submission:
N=int(input())
can=[]
for i in range(1,int(N**0.5)+1):
  if N%i==0:
    can.append(i-1+N//i-1)
    

print(min(can))
Buggy python submission (verdict: Runtime Error):
N=int(input())
print(0.5 if N%2==0 else ((N+1)/2)/((N-1)/2))

Fixed submission:
N=int(input())
print(0.5 if N%2==0 else ((N+1)/2)/N)
Buggy python submission (verdict: Time Limit Exceeded):
A,V=map(int,input().split())

answer=1
for i in range(2,min(A,V)+1):
    if A%i==V%i==0:
        answer+=1
    while A%i==0:
        A/=i
    while V%i==0:
        V/=i
    if min(A,V)<i:
        break


print(answer)

Fixed submission:
import fractions
A,B=map(int,input().split())
A,B=min(A,B),max(A,B)
g=fractions.gcd(A,B)
ans=1
for i in range(2,int(g**0.5+1)):
  if g%i==0:
    ans+=1
    while g%i==0:
      g/=i
    if g==1:
      break
if g!=1:
  ans+=1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
A,V=map(int,input().split())

answer=1
for i in range(2,min(A,V)+1):
    if A%i==V%i==0:
        answer+=1
    while A%i==0:
        A/=i
    while V%i==0:
        V/=i

print(answer)

Fixed submission:
import fractions
A,B=map(int,input().split())
A,B=min(A,B),max(A,B)
g=fractions.gcd(A,B)
ans=1
for i in range(2,int(g**0.5+1)):
  if g%i==0:
    ans+=1
    while g%i==0:
      g/=i
    if g==1:
      break
if g!=1:
  ans+=1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N,M=map(int,input().split())
key=[[] for _ in range(M)]
for i in range(M):
  A,B=map(int,input().split())
  key[i].append(A)
  C=list(map(int,input().split()))
  bit=0
  for c in C:
    bit+=2**(c-1)
  key[i].append(bit)

dp=[float("inf")]*(2**N)
dp[0]=0
ndp=[0]*(2**N)
for i in range(M):
  cost=key[i][0]
  bit=key[i][1]
  ndp=dp[:]
  for j in range(2**N):
  	ndp[bit|j]=min(dp[j]+cost,ndp[bit|j])
  dp=ndp[:]
 
print(dp[-1] if dp[-1]!=float("inf") else -1)
  

Fixed submission:
N,M=map(int,input().split())
key=[[] for _ in range(M)]
for i in range(M):
  A,B=map(int,input().split())
  key[i].append(A)
  C=list(map(int,input().split()))
  bit=0
  for c in C:
    bit+=2**(c-1)
  key[i].append(bit)

dp=[float("inf")]*(2**N)
dp[0]=0
ndp=[0]*(2**N)
for i in range(M):
  cost=key[i][0]
  bit=key[i][1]
  ndp=dp[:]
  for j in range(2**N):
  	ndp[bit|j]=min(dp[j]+cost,ndp[bit|j])
  dp=ndp[:]
 
print(dp[-1] if dp[-1]!=float("inf") else -1)
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
S=input()
ans=0
for i in range(N-1):
  #jstart=i+ans+1
  for j in range(i+1,N):
    if S[i:j] in S[j:]:
      ans=max(ans,j-i)
    else:
      break
print(ans)

Fixed submission:
N=int(input())
S=input()
ans=0
for i in range(N-1):
  jstart=i+ans+1
  for j in range(jstart,N):
    if S[i:j] in S[j:]:
      ans=max(ans,j-i)
    else:
      break
print(ans)

Buggy python submission (verdict: Runtime Error):
N=int(input())
S=input()
ans=0
for i in range(N-1):
  #jstart=i+ans+1
  for j in range(jstart,N):
    if S[i:j] in S[j:]:
      ans=max(ans,j-i)
    else:
      break
print(ans)

Fixed submission:
N=int(input())
S=input()
ans=0
for i in range(N-1):
  jstart=i+ans+1
  for j in range(jstart,N):
    if S[i:j] in S[j:]:
      ans=max(ans,j-i)
    else:
      break
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import bisect
N=int(input())
P=list(map(int,input().split()))

pos=[-1]*(N+1)

for i in range(N):
  pos[P[i]]=i
  
called=[-1,-1,pos[N],N,N]
ans=0
for i in range(N-1,0,-1):
  hoge=pos[i]
  r=bisect.bisect_left(called,hoge)
  R=called[r]
  RR=called[r+1]
  L=called[r-1]
  LL=called[r-2]
  ans+=i*((RR-R)*(hoge-L)+(L-LL)*(R-hoge))
  called=called[:r]+[hoge]+called[r:]
print(ans)
  


Fixed submission:
import bisect
N=int(input())
P=list(map(int,input().split()))

pos=[-1]*(N+1)

for i in range(N):
  pos[P[i]]=i
  
called=[-1,-1,pos[N],N,N]
ans=0
for i in range(N-1,0,-1):
  hoge=pos[i]
  r=bisect.bisect_left(called,hoge)
  R=called[r]
  RR=called[r+1]
  L=called[r-1]
  LL=called[r-2]
  ans+=i*((RR-R)*(hoge-L)+(L-LL)*(R-hoge))
  called.insert(r,hoge)
  #called=called[:r]+[hoge]+called[r:]
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
A=[list(map(int,input().split())) for _ in range(N)]
finish=[0]*N
day=0
tired=[False]*N
while 1:
  day+=1
  battle=False
  for i in range(N):
    tired[i]=False
    if finish[i]==N-1:
      continue
    enemy=A[i][finish[i]]-1
    if i==A[enemy][finish[enemy]]-1 and i>enemy and not tired[enemy]:
      finish[enemy]+=1
      finish[i]+=1
      tired[enemy]=True
      tired[i]=True
      battle=True
      #print("day:{0},{1}vs{2}".format(day,i+1,enemy+1))
  if battle==False:
    day-=1
    break
if min(finish)<N-1:
  print(-1)
else:
  print(day)




Fixed submission:
N=int(input())
A=[list(map(int,input().split())) for _ in range(N)]
wait=[[float("inf")]*N for _ in range(N)]
for i in range(N):
  wait[A[i][0]-1][i]=0
L=[list(range(N)),[]]
finish=[0]*N

day=0
ind=0
while L[ind]:
  battle=False
  day+=1
  for player in L[ind]:
    if finish[player]>=N-1:
      continue
    enemy=A[player][finish[player]]-1
    if wait[player][enemy]<day and wait[enemy][player]<day:
      battle=True
      #print("day{},{}vs{}".format(day,player+1,enemy+1))
      finish[player]+=1
      finish[enemy]+=1
      if finish[player]<N-1:
        wait[A[player][finish[player]]-1][player]=day
      if finish[enemy]<N-1:
        wait[A[enemy][finish[enemy]]-1][enemy]=day
      L[(ind+1)%2].append(player)
      L[(ind+1)%2].append(enemy)
  L[ind]=[]   
  ind=(ind+1)%2
  if not battle:
    day-=1
    break
if min(finish)<N-1:
  print(-1)
else:
  print(day)
Buggy python submission (verdict: Runtime Error):
def addScore(Point,Score):
    score[Point]+=Score
    min_index = binary_search(ab,Point)
    while min_index < n-1 and ab[min_index][0] == Point:
        addScore(ab[min_index][1],Score)
        min_index+=1
    

"""
minnum以上で最小の数のindexを返す。無いときはlen(list)を返す
計算量log(len(list))
"""

def binary_search(list, item):
    if list[0][0]>=item:
        return 0
    if list[-1][0]<item:
        return len(list)

    low = 0
    high = len(list) - 1

    while low <= high:
        mid = (low + high) //2
        guess = list[mid][0]
        if guess >= item and list[mid-1][0] < item:
            return mid
        if guess >= item:
            high = mid -1
        else:
            low = mid + 1

    return None






n,q=map(int,input().split())

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

ab.sort()

score=[0]*(n+1)

for _ in range(q):
    p,x=map(int,input().split())
    addScore(p,x)

print(*(score[1:]))

Fixed submission:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**9)
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()


n,q = na()
g = [[] for i in range(n)]
c = [0]*n

for i in range(n-1):
    a,b = na()
    g[a-1].append(b-1)
    g[b-1].append(a-1)
for i in range(q):
    p,x = na()
    c[p-1] += x

def f(b,a,r):
    r += c[a]
    c[a] = r
    for i in g[a]:
        if i != b:
            f(a,i,r)

f(-1,0,0)
print(' '.join([str(s) for s in c]))
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
List=list(map(int,input().split()))

count=0
for l in range(N):
    Left=Right=0
    for r in range(0,N-l):
        Left^=List[l+r]
        Right+=List[l+r]
        if Left==Right:
            count+=1
        elif Left<Right:
        	break

print(count)

Fixed submission:
N=int(input())
List=list(map(int,input().split()))

count=0
SumL=SumR=0
R=0
for L in range(N):
    if L>R:
        R=L
    while R<N and SumL^List[R]==SumR+List[R]:
        SumR+=List[R]
        SumL^=List[R]
        R+=1

    SumR-=List[L]
    SumL^=List[L]
    count += R-L

print(count)

Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
List=list(map(int,input().split()))

count=0
for l in range(N):
    Left=Right=0
    for r in range(0,N-l):
        Left^=List[l+r]
        Right+=List[l+r]
        if Left==Right:
            count+=1

print(count)

Fixed submission:
N=int(input())
List=list(map(int,input().split()))

count=0
SumL=SumR=0
R=0
for L in range(N):
    if L>R:
        R=L
    while R<N and SumL^List[R]==SumR+List[R]:
        SumR+=List[R]
        SumL^=List[R]
        R+=1

    SumR-=List[L]
    SumL^=List[L]
    count += R-L

print(count)

Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
List=list(map(int,input().split()))

count=0
for l in range(N):
    for r in range(l,N):
        Left=Right=List[l]
        for i in range(l+1,r+1):
            Left=Left^List[i]
            Right+=List[i]
        if Left==Right:
            count+=1

print(count)

Fixed submission:
N=int(input())
List=list(map(int,input().split()))

count=0
SumL=SumR=0
R=0
for L in range(N):
    if L>R:
        R=L
    while R<N and SumL^List[R]==SumR+List[R]:
        SumR+=List[R]
        SumL^=List[R]
        R+=1

    SumR-=List[L]
    SumL^=List[L]
    count += R-L

print(count)
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
a = [int(x) for x in input().split()]

ans = sum(a[0:k])
for i in range(1, n-k+1):
    nxt = sum(a[i:i+k])
    if ans < nxt:
        print('Yes')
    else:
        print('No')
    ans = nxt


Fixed submission:
n, k = map(int, input().split())
a = [int(x) for x in input().split()]

ans = sum(a[0:k])
for i in range(1, n-k+1):
    nxt = ans - a[i-1] + a[i+k-1]
    if ans < nxt:
        print('Yes')
    else:
        print('No')
    ans = nxt
Buggy python submission (verdict: Time Limit Exceeded):
T = list(input())

maxans = 0
ans = ''
def pdcount(t):
    return t.count('D') + t.count('PD')

tcnt = T.count('?')
for i in range(2**tcnt):
    L = []
    for j in range(tcnt):
        if (i >> j) &1 == 1:
            L.append('P')
        else:
            L.append('D')

    A = []
    pos = 0
    for k in range(len(T)):
        if T[k] == '?':
            A.append(L[pos])
            pos += 1
        else:
            A.append(T[k])
    
    if pdcount(''.join(A)) > maxans:
        ans = ''.join(A)
        maxans = pdcount(''.join(A))
print(ans)

Fixed submission:
t = input()
print(t.replace('?', 'D'))
Buggy python submission (verdict: Runtime Error):
from itertools import combinations

n, m, q = map(int, input().split())
comb = list(combinations(range(1, m+1), n))
ans = [0] * len(comb)
for _ in range(q):
    a, b, c, d = map(int, input().split())
    for i in range(len(comb)):
        if comb[i][b-1] - comb[i][a-1] == c:
            ans[i] += d
print(max(ans))

Fixed submission:
from itertools import combinations_with_replacement

n, m, q = map(int, input().split())
comb = list(combinations_with_replacement(range(1, m+1), n))
ans = [0] * len(comb)
for _ in range(q):
    a, b, c, d = map(int, input().split())
    for i in range(len(comb)):
        if comb[i][b-1] - comb[i][a-1] == c:
            ans[i] += d
print(max(ans))