Harryxun/stf_run huggingface dataset:
#再帰を使って各ノードのカウンタの値を決定
def dfs(v,p,G,c):#vは0始まり
    for u in G[v]:
        if u!=p:
            c[u]+=c[v]
            dfs(u,v,G,c) 

N,Q = list(map(int,input().split()))

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

p=[0]*Q
x=[0]*Q
for i in range(Q):
    p[i],x[i] = list(map(int,input().split()))
    p[i]-=1
    
c=[0]*N
for i in range(Q):
    c[p[i]] += x[i]

dfs(0,-1,G,c)

ans = ' '.join([str(x) for x in c])

print(ans)

### FIXED CODE ###

'''
pythonの再帰は10^5timesですら厳しい
import sys
sys.setrecursionlimit(10000000)

def dfs(v,p,G,c):
    for u in G[v]:
        if u!=p:
            c[u]+=c[v]
            dfs(u,v,G,c) 
'''
from collections import deque

N,Q = list(map(int,input().split()))

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

p=[0]*Q
x=[0]*Q
c=[0]*N
for i in range(Q):
    p,x = list(map(int,input().split()))
    p-=1
    c[p] += x

stack=deque([0])
parent = [-1]*N

while(stack):
    v = stack.pop()
    for u in G[v]:
        if u!=parent[v]:
            c[u]+=c[v]
            parent[u]=v
            stack.appendleft(u)


ans = ' '.join([str(x) for x in c])

print(ans)
import sys
H,W=map(int,input().split())
listA=[list(input()) for i in range(H)]
start=[0,0]
while 1:
  if start==[H-1,W-1]:
    print("Possible")
    sys.exit()
  if start[0]!=H-1 and listA[start[0]+1][start[1]]=="#" and listA[start[0]][start[1]+1]=="#":
    print("Impossible")
    sys.exit()
  if start[0]!=0 and start[1]!=0 and listA[start[0]-1][start[1]]=="#" and listA[start[0]][start[1]-1]=="#":
    print("Impossible")
    sys.exit()
  if start[0]!=H-1 and listA[start[0]+1][start[1]]=="#":
    start=[start[0]+1,start[1]]
    continue  
  if start[1]!=W-1 and listA[start[0]][start[1]+1]=="#":
    start=[start[0],start[1]+1]    
  else:
    print("Impossible")

### FIXED CODE ###

import sys
H,W=map(int,input().split())
listA=[list(input()) for i in range(H)]
start=[0,0]
while 1:  
  if start[0]!=H-1 and start[1]!=W-1 and listA[start[0]+1][start[1]]=="#" and listA[start[0]][start[1]+1]=="#":
    print("Impossible")
    sys.exit()
  if start[0]!=0 and start[1]!=0 and listA[start[0]-1][start[1]]=="#" and listA[start[0]][start[1]-1]=="#":
    print("Impossible")
    sys.exit()
  if start==[H-1,W-1]:
    print("Possible")
    sys.exit()  
  if start[0]!=H-1 and listA[start[0]+1][start[1]]=="#":
    start=[start[0]+1,start[1]]
    continue  
  if start[1]!=W-1 and listA[start[0]][start[1]+1]=="#":
    start=[start[0],start[1]+1]    
  else:
    print("Impossible")
K = int(input().split()[1])
As = [int(i) for i in input().split()]
As.sort(reverse=True)
bit_num = len(bin(K))-2
arr = [[int(s) for s in format(val,'b').zfill(bit_num)] for val in As]
arr = [sum([arr[i][j] for i in range(len(arr))]) for j in range(len(arr[0]))]
ans = int("".join(["0" if i>len(arr)/2 else "1" for i in arr]), 2)
ans = ans if ans < K else K
print(sum([ans^i for i in As]))

### FIXED CODE ###

str_ = input().split()
x = int(str_[0])
t = int(str_[1])
print(x/t)
b = input()

if b == 'A':
    print('T')
elif b == 'T':
    print('A')
    
elif B == 'G':
    print('C')
else:
    print('G')

### FIXED CODE ###

b = input()

if b == 'A':
    print('T')
elif b == 'T':
    print('A')
    
elif b == 'G':
    print('C')
else:
    print('G')
from sys import stdin

N, K = map(int, input().rstrip().split())
A = [int(x) for x in stdin.readline().rstrip().split()]

def is_max_len_less_than_input(x,K,A):
  count = 0
  for ln in A:
    count += int(ln/x)
    if count > K:
      return False
  return True

def binary_search(begin,end,K,A):
  while abs(end-begin)>1:
    mid = int((begin+end)/2+1)
    if is_max_len_less_than_input(mid,K,A):
      end = mid
    else:
      begin = mid
  return mid

print(binary_search(1,max(A),K,A))
# 最小値は1 => 0除算を回避


### FIXED CODE ###

from sys import stdin
from math import floor,ceil

N, K = map(int, input().rstrip().split())
A = [int(x) for x in stdin.readline().rstrip().split()]

def is_max_len_less_than_input(x,K,A):
  count = 0
  if x==0:
    return False
  for ln in A:
    count += ceil(ln/x)-1
    if count > K:
      return False
  return True

def binary_search(begin,end,K,A):
  while abs(end-begin)>1:
    mid = (begin+end)//2
    if is_max_len_less_than_input(mid,K,A):
      end = mid
    else:
      begin = mid
  return end

print(binary_search(0,max(A),K,A))
a,b,c,d,e,k = map(int, input().split())
print(':(' if e-a > k else "Yay!")


### FIXED CODE ###

a,b,c,d,e,k = [int(input()) for _ in range(6)]
print(':(' if e-a > k else "Yay!")
s = input()
ans = 0
cnt = 0
while(cnt < len(s)-2):
  if s[cnt] == s[cnt+1]:
    cnt += 3
    ans += 2
  else:
    cnt += 1
    ans += 1
if s[cnt] == s[cnt+1]:
  ans += 1
else:
  ans += 2
print(ans)

### FIXED CODE ###

k=0
s=t=''
for c in input():
  s+=c
  if s!=t:
    k+=1
    s,t='',s
print(k)
N,K = map(int,input().split())

price = list(map(int,input(),split()))

price.sort

for p in range(1,K):
	ans  += price[p]

print(ans)


### FIXED CODE ###

N,K = map(int,input().split())

price = list(map(int,input().split()))

price.sort()

ans = sum(price[:K])
print(ans)
n,b,r = map(int, input().split())
s = n // (b+r)
a = n % (b+r)
ans = s * b
ans += min(a, b)
print({}.format(ans))

### FIXED CODE ###

n,b,r = map(int, input().split())
s = n // (b+r)
a = n % (b+r)
ans = s * b
ans += min(a, b)
print("{}".format(ans))
x,k,d=map(int,input().split())
xa=abs(x)
pm=x//xa
kz=xa//d
xz=xa-kz*d
if xz*2>d:
  xzz=d-xz
  kz+=1
else:
  xzz=xz
rest=k-kz
if rest%2==0:
  print(xzz)
else:
  print(d-xzz)
  

### FIXED CODE ###

x,k,d=map(int,input().split())
xa=abs(x)
kz=xa//d
xz=xa-kz*d

if xz*2>d:
  xzz=d-xz
  kz+=1
else:
  xzz=xz
rest=k-kz
if rest<0:
  print(xa-k*d)
elif rest%2==0:
  print(xzz)
else:
  print(d-xzz)
def combinationListRecursive(data, r):
  if r == 0 or r > len(data):
    return []

  result = []
  _combinationListRecursive(data, r, 0, [], result)
  return result


def _combinationListRecursive(data, r, start, progress, result):
  if r == 0:
    result.append(progress)
    return

  for i in range(start, len(data)):
    _combinationListRecursive(data, r - 1, i + 1, progress + [data[i]], result)

def plus(l1, l2):
    return [x + y for (x, y) in zip(l1, l2)]


# 整数の入力
N, M = list(map(int, input().split(" ")))

l = []
for n in range(N):
    l.append(list(map(int, input().split(" "))))

ind_list = list(range(N))

if M == 0:
    print(0)

else:
    # NからMを選ぶ
    comb_list = combinationListRecursive(ind_list, M)
    # print(comb_list)

    max_kachi = 0
    for comb in comb_list:
        l_ = [0, 0, 0]
        for i in comb:
            l_ = plus(l_, l[i])

        kachi = abs(l_[0]) + abs(l_[1]) + abs(l_[2])
        max_kachi = max(max_kachi, kachi)

    print(max_kachi)




### FIXED CODE ###

def plus(l1, l2):
    return [x + y for (x, y) in zip(l1, l2)]


# 整数の入力
N, M = list(map(int, input().split(" ")))

cake_list = []
for n in range(N):
    cake_list.append(list(map(int, input().split(" "))))


# 正の値、負の値で8パターン考えれば良い。
plus_minus_list = [[1, 1, 1], [1, 1, -1], [1, -1, 1], [-1, 1, 1],
                   [1, -1, -1], [-1, 1, -1], [-1, -1, 1], [-1, -1, -1]]


pattern_sum_list = []
for pattern in plus_minus_list:
    pattern_sum = 0
    cake_num_list = []
    for cake in cake_list:
        cake_num = cake[0]*pattern[0]+cake[1]*pattern[1]+cake[2]*pattern[2]
        cake_num_list.append(cake_num)

    cake_num_list = sorted(cake_num_list)[::-1]
    pattern_sum_list.append(sum(cake_num_list[:M]))

print(max(pattern_sum_list))
a=int(input())
if a==1:
  print("Hello World")
b=int(input())
c=int(input())

if a==2:
  print(int(b+c))

### FIXED CODE ###

a=int(input())
if a==1:
  print("Hello World")
else:
  b=int(input())
  c=int(input())
  print(int(b+c))
list = list(map(int,input().split(" ")))

X = []
cnt = 0
for i in range(1, 1 + int(min(list[0],list[1]))):
  if(list[0] % i == 0 and list[1] % i == 0):
    X.append(i)
    cnt = 1
X.sorted(reverse)
if (cnt == 1):
  print(X[list[2]-1])
else:
  print(1)

### FIXED CODE ###

list = list(map(int,input().split(" ")))

X = []
cnt = 0
for i in range(1, 1 + int(min(list[0],list[1]))):
  if(list[0] % i == 0 and list[1] % i == 0):
    X.append(i)
    cnt = 1
X.sort(reverse=True)
if (cnt == 1):
  print(X[list[2]-1])
else:
  print(1)
from fractions import gcd

def x(k, c, d):
    rl1 = k
    lcm = c*d / math.gcd(c,d)
    ccount = int(rl1 // c)
    dcount = int(rl1 // d)
    if lcm != 0:
        cdcount = int(rl1 // lcm)
    else:
        cdcount = 0

    return int(rl1 - ccount - dcount + cdcount)

a, b, C, D = map(int, input().split())
print(x(b, C, D) - x(a-1, C, D))

### FIXED CODE ###

import fractions

def x(k, c, d):
    rl1 = k
    lcm = c*d // fractions.gcd(c,d)
    ccount = rl1 // c
    dcount = rl1 // d
    cdcount = rl1 // lcm
    # if lcm != 0:
    #     cdcount = int(rl1 // lcm)
    # else:
    #     cdcount = 0

    return rl1 - ccount - dcount + cdcount

a, b, C, D = map(int, input().split())
print(x(b, C, D) - x(a-1, C, D))
def solve(j,sum):
    print j, sum
    if j==n-1:
        ans[sum] = 1
        if sum+A[j] <= 2000:
            ans[sum+A[j]] = 1
    solve(j+1,sum)
    if sum+A[j] <= 2000:
        solve(j+1,sum+A[j])

n=int(input())
A=[]*n
A=list(input().split())
for i in range(n):
    A[i]=int(A[i])
ans=[0]*2001    
solve(0,0)   

m=int(input())
B=list(input().split())
for i in range(m):
    B[i]=int(B[i])
for i in range(m):
    if ans[B[i]]==1:
        print("yes")
    else:
        print("no")


### FIXED CODE ###

n = int(input())
A = list(map(int,input().split()))
m = int(input())
B = list(map(int,input().split()))

T = [[0]*2001 for i in range(n)]

T[0][0] = 1
T[0][A[0]] = 1
for i in range(1,n):
    for j in range(2001):
        T[i][j] = T[i-1][j]
        if (j - A[i] >=0) and (T[i-1][j-A[i]] == 1):
            T[i][j] = 1
    
for i in range(m):
    if T[n-1][B[i]] == 1: print("yes")
    else: print("no")
W, H, x, y, r = input().split()

if x + r > W or y + r > H or x - r < 0 or y - r < 0:
    print("No")
else :
    print("Yes")

### FIXED CODE ###

W, H, x, y, r = [int(i) for i in input().split()]

if x + r > W or y + r > H or x - r < 0 or y - r < 0:
    print("No")
else :
    print("Yes")
N=int(input())
L=list(map(int,input().split()))
cnt=0
while all(l%2==0 l in L):
  L=[l/2 for l in L]
  cnt+=1
print(cnt)

### FIXED CODE ###

N=int(input())
L=list(map(int,input().split()))
cnt=0
while all(l%2==0 for l in L):
  L=[l/2 for l in L]
  cnt+=1
print(cnt)
a = int(input())
b = int(input())
c = int(input())
d = int(input())
A = [i for i in range(a, b + 1)]
B = [i for i in range(c, d + 1)]
for i in A:
    if i in B:
        a = True
        break
if a == True:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

k=int(input())
print("ACL" * k)
N,M=map(int,input().split())
n1=min(N,M//2)
N-=n1
M-=2*n1

if N==0:
  ans=n1+M//4
else:
  ans=n1+N//2
  raise ValueError()
print(ans)


### FIXED CODE ###

N,M=map(int,input().split())
n1=min(N,M//2)
print(n1+(M-2*n1)//4)
N = int(input())
S = input()
K = int(input())
M = str()
for i in range(N):
    if S[i] != S[K]:
        M= M +"*"
    else:
        M= M +S[i]
print(M)

### FIXED CODE ###

N = int(input())
S = input()
K = int(input())
M = str()
for i in range(N):
    if S[i] != S[K-1]:
        M= M +"*"
    else:
        M= M +S[i]
print(M)
# -*- coding:utf-8 -*-
"""考え方
   i:    0 1   2 3   4
------------------  
A[i]:  100 2 100 2 100

iが奇数のときのA[i]をまず減らす戦略が有効。

その後、まだ条件を満たさないなら、iが偶数のときのA[i]を減らす。

"""
def solve():
    N, x = list(map(int, input().split()))
    A = list(map(int, input().split()))

    ans = 0
    for i in range(1, N, 2):

        # iが奇数のときの数字を減らす。
        if A[i-1]+A[i] > x:
            diff = (A[i-1]+A[i]) - x
            if A[i] <= diff:
                A[i] -= diff
                ans += diff
    
    for i in range(0, N, 2):
        if i == N-1:
            if A[i]+A[i-1] > x:
                diff = (A[i]+A[i-1]) - x
                A[i] -= diff
                ans += diff

        # iが偶数のときの数字を減らす
        if A[i]+A[i+1] > x:
            diff = (A[i]+A[i+1]) - x
            A[i] -= diff
            ans += diff
    
    print(ans)


if __name__ == "__main__":
    solve()


### FIXED CODE ###

# -*- coding:utf-8 -*-
"""貪欲法
"""
def solve():
    N, x = list(map(int, input().split()))
    A = list(map(int, input().split()))

    ans = 0

    total = A[1] + A[0]
    if total > x:
        diff = min(total-x, A[1])
        A[1] -= diff
        ans += diff

    total = A[1] + A[0]
    if total > x:
        diff = total - x
        A[0] -= diff
        ans += diff

    for i in range(2, N):
        total = A[i] + A[i-1]

        if total > x:
            diff = total - x
            A[i] -= diff
            ans += diff
    
    print(ans)


if __name__ == "__main__":
    solve()
#!/usr/bin/env python3
import sys


def solve(M: int, K: int):
    if M == 0:
        if K == 0:
            print('0 0')
        else:
            print(-1)
    elif M == 1:
        if K == 0:
            print('0 0 1 1')
        else:
            print(-1)
    else:
        if K > 2 ** M:
            print(-1)
        else:
            l = list(range(2 ** M))
            l.pop(K)
            print(' '.join(l), end=' ')
            print(K, end=' ')
            print(' '.join(l[::-1]), end=' ')
            print(K)
    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools
# (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    M = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    solve(M, K)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(M: int, K: int):
    if M == 0:
        if K == 0:
            print('0 0')
        else:
            print(-1)
    elif M == 1:
        if K == 0:
            print('0 0 1 1')
        else:
            print(-1)
    else:
        if K >= 2 ** M:
            print(-1)
        else:
            ans = [i for i in range(2 ** M) if i != K]
            ans = ans + [K] + ans[::-1] + [K]
            print(*ans)
    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools
# (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    M = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    solve(M, K)


if __name__ == '__main__':
    main()
from numpy import *
N,W=map(int,input().split())
dp=zeros(W+1,int)
for i in range(N):
    w,v=map(int,input().split())
    dp[w:]=maximum(dp[:-w]+v,dp[w:])
print(dp[-1])

### FIXED CODE ###

import numpy as np
N,W=map(int,input().split())
dp=np.full(10**5+1,W+1)
dp[0]=0
for i in range(N):
    w,v=map(int,input().split())
    dp[v:]=np.minimum(dp[:-v]+w,dp[v:])
print(np.max(np.where(dp<=W)))
N=int(input())
A=list(map(int,input().split()))
ans = []
for i in reversed(range(1, N+1)):
    a = A[i-1]
    for j in range(2, N+1):
        tmp = i * j
        if tmp > N:
            break
        a %= A[tmp-1]
    if a % 2 == 1:
        ans.append(i)
    A[i-1] = a % 2
print(len(ans))
for a in ans:
    print(a)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
B=[0] * N
ans = []
for i in reversed(range(1, N+1)):
    a = A[i-1]
    for j in range(1, N+1):
        tmp = i * j
        if tmp > N:
            break
        a += B[tmp-1]
    if a % 2 == 1:
        ans.append(i)
    B[i-1] = a % 2
print(len(ans))
for a in ans:
    print(a)
print(input().count('2')

### FIXED CODE ###

print(input().count('2'))
N = int(input())

count = 0
for i in range(1,N+1):
  if len(str(i))%2=1:
    count += 1

print(count)

### FIXED CODE ###

N = int(input())

count = 0
for i in range(1,N+1):
  a = [_ for _ in str(i)]
  if len(a)%2==1:
    count += 1

print(count)
a, b, c, d = map(int, input().split())
print(max(a*c, a*d, b*c, b*d))


### FIXED CODE ###

N = int(input())
ans = N*(N-1)
mod = 10**9 + 7
ans %= mod
ans = 1
A = 1
B = 1
C = 1
for i in range(N):
    A *= 10
    B *= 9
    C *= 8
    A %= mod
    B %= mod
    C %= mod

print((A-B*2+C) % mod)
from math import sqrt

i = input().split()
a = int(i[0] * (10 ** 10))
b = int(i[1]* (10 ** 10))
c = int(i[2]* (10 ** 10))

if sqrt(a) + sqrt(b) < sqrt(c):
    print("Yes")
else:
    print("No")

### FIXED CODE ###

from math import sqrt

i = input().split()
a = int(i[0])
b = int(i[1])
c = int(i[2])

d = (c - b - a) > 0
e = (c - b - a) ** 2 > 4 * a * b

if d and e:
    print("Yes")
else:
    print("No")
import sys
input = lambda: sys.stdin.readline().rstrip() 

def resolve():
    H, W = map(int, input().split())
    s = [input() for _ in range(H)]

    ans = [[0]*W for _ in range(H)]
    if s[0][0]=='#':
        ans[0][0] = 1
    for i in range(1, W+H):
        for j in range(max(W, H)):
            if 0<=i-j<min(W, H):
                if j==0:
                    if s[j][i-j-1]=='.' and s[j][i-j]=='#':
                        ans[j][i-j] = ans[j][i-j-1] + 1
                    else:
                        ans[j][i-j] = ans[j][i-j-1]
                elif i-j==0:
                    if s[j-1][i-j]=='.' and s[j][i-j]=='#':
                        ans[j][i-j] = ans[j-1][i-j] + 1
                    else:
                        ans[j][i-j] = ans[j-1][i-j]
                else:
                    if (s[j-1][i-j]=='.' or s[j][i-j-1]=='.') and s[j][i-j]=='#':
                        ans[j][i-j] = min(ans[j-1][i-j], ans[j][i-j-1]) + 1
                    else:
                        ans[j][i-j] = min(ans[j-1][i-j], ans[j][i-j-1])
    # print(ans)
    print(ans[-1][-1])

if __name__ == '__main__':
    resolve()

### FIXED CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip() 

def resolve():
    H, W = map(int, input().split())
    s = [input() for _ in range(H)]

    ans = [[0]*W for _ in range(H)]
    if s[0][0]=='#':
        ans[0][0] = 1
    for i in range(1, W+H-1):
        for y in range(max(0, i-(W-1)), min(i+1, H)):
            x = i-y
            if y==0:
                if s[y][x-1]=='.' and s[y][x]=='#':
                    ans[y][x] = ans[y][x-1] + 1
                else:
                    ans[y][x] = ans[y][x-1]
            elif x==0:
                if s[y-1][x]=='.' and s[y][x]=='#':
                    ans[y][x] = ans[y-1][x] + 1
                else:
                    ans[y][x] = ans[y-1][x]
            else:
                if s[y][x]=='#':
                    ans[y][x] = min(ans[y-1][x]+(1 if s[y-1][x]=='.' else 0), ans[y][x-1]+(1 if s[y][x-1]=='.' else 0))
                else:
                    ans[y][x] = min(ans[y-1][x], ans[y][x-1])
    print(ans[-1][-1])

if __name__ == '__main__':
    resolve()
n=input()
satis=[]

for i in range(n):
  A=list(map(int,input().split()))
  satis.extend(A)

tempA=satis[0]
tempB=satis[1]
tempC=satis[2]
if n > 1:
  for i in range(n-1):
    tempA2=satis[3*i+3]+max([tempB,tempC])
    tempB2=satis[3*i+4]+max([tempA,tempC])
    tempC2=satis[3*i+5]+max([tempA,tempB])
    tempA=tempA2
    tempB=tempB2
    tempC=tempC2
  print(max([tempA,tempB,tempC]))
else:
  print(max([tempA,tempB,tempC]))

### FIXED CODE ###

n=int(input())
satis=[]

for i in range(n):
  A=list(map(int,input().split()))
  satis.extend(A)

tempA=satis[0]
tempB=satis[1]
tempC=satis[2]
if n > 1:
  for i in range(n-1):
    tempA2=satis[3*i+3]+max([tempB,tempC])
    tempB2=satis[3*i+4]+max([tempA,tempC])
    tempC2=satis[3*i+5]+max([tempA,tempB])
    tempA=tempA2
    tempB=tempB2
    tempC=tempC2
  print(max([tempA,tempB,tempC]))
else:
  print(max([tempA,tempB,tempC]))
n = int(input())
p = [int(input()).for i in range(n)]
print(sam(p)-p[-1]/2)

### FIXED CODE ###

n = int(input())
p = [int(input()) for i in range(n)]
print(sum(p)-max(p)//2)
s = input()
k = input()
l = input()
d = l/k
j = l % k
if s > k :  
  if j !=:
    d += 1
    print(d)
else:
  print(d)

### FIXED CODE ###

s = input()
k = input()
l = input()
if s > k :
        d = l/s
        j = l % s
        if j != 0:
                d += 1
                print(d)
        else:
                print(d)
else:
        d = l/k
        j = l % k
        if j != 0:
                d += 1
                print(d)
        else:
                print(d)
N = int(input())
AC = 0
WA = 0
TLE = 0
RE = 0
for i in range(N):
    s = input()
    if s == 'AC':
        AC += 1
    elif s == 'WA':
        WA += 1
    elif s == 'TLE':
        TLE += 1
    else:
        RE += 1
print('AC','×',AC)
print('WA','×',WA)
print('TLE','×',TLE)
print('RE','×',RE)
    

### FIXED CODE ###

N = int(input())
if N % 1000 > 0:
    print(1000 - (N % 1000))
elif N % 1000 == 0:
    print(0)
from math import ceil
from heapq import heapify, heappop, heappush

N, K, *A = map(int, open(0).read().split())

a = [(-i, i, 1) for i in A]
heapify(a)
while K != 0:
    i, j, k = heappop(a)
    #print(i, j, k)
    t = -a[0][0]
    nk = ceil(j / t)
    t = max(min(nk - k, K), 1)
    K -= t
    k += t
    i = -(j / k)
    heappush(a, (i, j, k))
    #print(i, j, k)
print(ceil(heappop(a)[0] * -1))


### FIXED CODE ###

from math import ceil

N, K, *A = map(int, open(0).read().split())

def is_ok(n):
    t = 0
    for a in A:
        if a <= n:
            continue
        t += ceil(a / n) - 1
    return t <= K

ok = 1000000000
ng = 0.0000000001
while abs(ng - ok) > 1:
    m = (ok + ng) // 2
    if is_ok(m):
        ok = m
    else:
        ng = m

print(ceil(ok))
n,m=[int(i) for i in input().split()]
P=[[int(i) for i in input().split()] for j in range(m)]

def prefecturesort(i):
    return i[0]

def yearsort(i):
    return i[1]

W=[0 for i in range(n)]
Z=[]

for i in range(m):
    P[i].append(i)
    W[P[i][0]]+=1

P.sort(key=prefecturesort)
P_c=[]
sum=0
for i in range(n):
    c=W[i]
    if c==0:
        P_c.append([])
    else:
        P_c.append(P[sum:c+sum])
    sum+=c
    P_c[i].sort(key=yearsort)
for x in P_c:
    for j in range(len(x)):
        X=str("{0:06d}".format(x[j][0]))
        Y=str("{0:06d}".format(j+1))
        Z.append([X+Y,x[j][2]])
Z.sort(key=yearsort)
for i in range(m):
    print(Z[i][0])


### FIXED CODE ###

n,m=[int(i) for i in input().split()]
P=[[int(i) for i in input().split()] for j in range(m)]

def prefecturesort(i):
    return i[0]

def yearsort(i):
    return i[1]

W=[0 for i in range(n)]
Z=[]

for i in range(m):
    P[i].append(i)
    W[P[i][0]-1]+=1

P.sort(key=prefecturesort)
P_c=[]
sum=0
for i in range(n):
    c=W[i]
    if c==0:
        P_c.append([])
    else:
        P_c.append(P[sum:c+sum])
    sum+=c
    P_c[i].sort(key=yearsort)
for x in P_c:
    for j in range(len(x)):
        X=str("{0:06d}".format(x[j][0]))
        Y=str("{0:06d}".format(j+1))
        Z.append([X+Y,x[j][2]])
Z.sort(key=yearsort)
for i in range(m):
    print(Z[i][0])
n=int(input())
c=str(input())
c=c[::-1]
#print(c)
c_count=[]
count1=0
count2=0
for i in range(n):
    if c[i]=='.':
        start=i
        break
else:
    print(0)


for i in range(start,n):
    if c[i]=='.':
        if count2!=0:
            c_count.append(count2)
            count2=0
        count1+=1
    else:
        if count1!=0:
            c_count.append(count1)
            count1=0
        count2+=1
        
c_count.append(max(count1,count2))

#print(c_count)
ans=0
for i in range(0,len(c_count)-1,2):
    ans+=min(c_count[i],c_count[i+1])
print(ans)

### FIXED CODE ###

n=int(input())
c=str(input())
#c=c[::-1]
#print(c)
black=c.count('#')
white=n-black
left=0#左は黒を消す
right=white#右はしろを消す
#print(white,black)
ans=right
for i in range(n):
    if c[i]=='#':
        left+=1
    else:
        right-=1
    
    ans=min(ans,left+right)
print(ans)