Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

n=int(input())
s=input()
a=[0]
for i in s:
    if i==".":a+=[a[-1]+1]
    else:a+=[a[-1]]
print(min(i-a[i]*2+s.count(".") for i in range(n+1)))

### FIXED CODE ###

ans=n=int(input())
s=input()
a=[0]
for i in s:
    if i==".":
        a+=[a[-1]+1]
    else:
        a+=[a[-1]]
w=s.count(".")
for i in range(n+1):
    ans=min(ans,i-a[i]+w-a[i])
print(ans)
### BUGGY CODE ###

class SegmentTree():
    def __init__(self, values, merge_func=min, default=float("inf")):
        n = len(values)
        self.size = 1
        self.default = default
        self.merge = merge_func
        while self.size < n:
            self.size *= 2
        # tree[0] = empty
        # child of tree[n] = tree[n*2], tree[n*2+1]
        self.tree = [self.default] * self.size * 2
        for i in range(n):
            self.tree[self.size + i] = values[i]
        for i in range(self.size-1, 0, -1):
            self.tree[i] = self.merge(self.tree[i*2], self.tree[i*2+1])

    def __query(self, a, b, k, l, r):
        if r <= a or b <= l:
            return self.default
        if a <= l and r <= b:
            return self.tree[k]
        left = self.__query(a, b, k*2, l, (l+r)//2)
        right = self.__query(a, b, k*2+1, (l+r)//2, r)
        return self.merge(left, right)

    # query segmentation value of [a, b)
    def query(self, a, b):
        return self.__query(a, b, 1, 0, self.size)


def main():
    N, K = map(int, input().split())
    P = list(map(int, input().split()))
    seq = 1
    for i in range(K-1):
        if P[i] < P[i+1]:
            seq += 1
        else:
            seq = 1
    has_orig = seq == K
    rmq = SegmentTree(P)
    rMq = SegmentTree(P, merge_func=max, default=-1)
    ans = 1
    for i in range(N-K):
        if P[i+K-1] < P[i+K]:
            seq += 1
        else:
            seq = 1
        if seq >= K:
            if not has_orig:
                has_orig = True
                ans += 1
            continue
        if P[i] != rmq.query(i, i+K+1) or P[i+K] != rMq.query(i, i+K+1):
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import math


def main():
    N, K = map(int, input().split())
    P = list(map(int, input().split()))
    seq = 1
    for i in range(K-1):
        if P[i] < P[i+1]:
            seq += 1
        else:
            seq = 1
    has_orig = seq == K
    ln = int(math.log(K, 2))
    dp1 = [[0] * N for _ in range(ln+1)]
    dp2 = [[0] * N for _ in range(ln+1)]
    dp1[0] = P
    dp2[0] = P
    for k in range(ln):
        for i in range(N-2**k):
            dp1[k+1][i] = min(dp1[k][i], dp1[k][i+2**k])
            dp2[k+1][i] = max(dp2[k][i], dp2[k][i+2**k])
    rmq = [float("inf")] * (N-K+1)
    rMq = [0] * (N-K+1)
    for i in range(N-K+1):
        idx = i
        for k in range(ln+1)[::-1]:
            if K & (2**k):
                rmq[i] = min(rmq[i], dp1[k][idx])
                rMq[i] = max(rMq[i], dp2[k][idx])
                idx += 2**k
    ans = 1
    for i in range(N-K):
        if P[i+K-1] < P[i+K]:
            seq += 1
        else:
            seq = 1
        if seq >= K:
            if not has_orig:
                has_orig = True
                ans += 1
            continue
        if P[i] != rmq[i] or P[i+K] < rMq[i]:
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()
### BUGGY CODE ###

H, W, N = map(int, raw_input().split())
D = dict()

for i in range(N):
    a, b = map(int, raw_input().split())
    for a_add in [-1, 0, 1]:
        for b_add in [-1, 0, 1]:
            c = a + a_add
            d = b + b_add
            if c-1 in range(1, H-1) and d-1 in range(1, W-1):
                if str([c, d]) in D.keys():
                    D[str([c, d])] += 1
                else:
                    D[str([c, d])] = 1

res_list = [0]*10
for s in D.keys():
    res_list[D[s]] += 1

res_list[0] = (H-2) * (W-2) - sum(res_list)

for i in range(10):
    print res_list[i]

### FIXED CODE ###

H, W, N = map(int, raw_input().split())
D = dict()

for i in range(N):
    a, b = map(int, raw_input().split())
    for a_add in [-1, 0, 1]:
        for b_add in [-1, 0, 1]:
            c = a + a_add
            d = b + b_add
            if c-1 in range(1, H-1) and d-1 in range(1, W-1):
                if D.has_key(str([c, d])):
                    D[str([c, d])] += 1
                else:
                    D[str([c, d])] = 1

res_list = [0]*10
for s in D.keys():
    res_list[D[s]] += 1

res_list[0] = (H-2) * (W-2) - sum(res_list)

for i in range(10):
    print res_list[i]
### BUGGY CODE ###

N=int(input())
AList = [int(input()) for i in range(N)]

if AList.count(max(AList)) > 1:
    for i in range(N):
        print(max(AList))
else:
    SList=sorted(AList)
    SecMax=SList[-2]
    MaxIndex=AList.index(max(AList))
    
    for i in range(N):
        if i==MaxIndex:
            print(SecMax)
        else:
            print(max(AList))
    
    
    


### FIXED CODE ###

N = int(input())
A = []
for i in range(N):
    A.append(int(input()))
B = sorted(A)
for n in A:
    if B[-1] != n:
        print(B[-1])
    else:
        print(B[-2])
### BUGGY CODE ###

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

data = [0]*(N+1)
def add(k, x):
    while k <= N:
        data[k] += x
        k += k & -k

def get(k):
    s = 0
    while k:
        s += data[k]
        k -= k & -k
    return s

# 二分探索
N0 = 2**(N-1).bit_length()
def lower_bound(x):
    w = i = 0
    k = N0
    while k:
        if i+k <= N and w + data[i+k] <= x:
            w += data[i+k]
            i += k
        k >>= 1
    return i+1

c=[int(i) for i in input().split()]
Q=[]
for i in range(q):
    l,r=map(int,input().split())
    Q.append((l,r,i))
Ans=[0 for i in range(q)]
F=[-1 for i in range(5*10**5+1)]
Q.sort(key=lambda x:x[1])
Q.append((10**6,10**6,10**6))

for i in range(n):
    add(i+1,1)

quen=0
for i in range(n):
    if F[c[i]]>=0:
        add(F[c[i]]+1,-1)
    F[c[i]]=i
    while Q[quen][1]==i+1:
        Ans[Q[quen][2]]=-get(Q[quen][0]-1)+get(Q[quen][1])
        #print(Tre.query(Q[quen][0]-1,Q[quen][1]))
        quen+=1

for ele in Ans:
    print(ele)

### FIXED CODE ###

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

data = [0]*(N+1)
def add(k, x):
    while k <= N:
        data[k] += x
        k += k & -k

def get(k):
    s = 0
    while k:
        s += data[k]
        k -= k & -k
    return s

c=[int(i) for i in input().split()]
Q=[]
for i in range(q):
    l,r=map(int,input().split())
    Q.append((l,r,i))
Ans=[0 for i in range(q)]
F=[-1 for i in range(5*10**5+1)]
Q.sort(key=lambda x:x[1])
#Q.append((10**6,10**6,10**6))

for i in range(n):
    add(i+1,1)

"""
quen=0
nowQ=Q[quen]
for i in range(n):
    ci=c[i]
    if F[ci]>=0:
        add(F[ci]+1,-1)
    F[ci]=i
    while nowQ[1]==i+1:
        Ans[nowQ[2]]=-get(nowQ[0]-1)+get(nowQ[1])
        quen+=1
        nowQ=Q[quen]
    if nowQ[1]==10**6:
        break
"""

i=0
for nowQ in Q:
    while nowQ[1]!=i:
        ci=c[i]
        if F[ci]>=0:
            add(F[ci]+1,-1)
        F[ci]=i
        i+=1
    Ans[nowQ[2]]=-get(nowQ[0]-1)+get(nowQ[1])


print("\n".join([str(i) for i in Ans]))
### BUGGY CODE ###

from bisect import insort_left
N, M = map(int, input().split())
A = list(map(int, input().split()))

A.sort()
for _ in range(M):
    a = A.pop()
    insort_left(A, a//2)
    
print(sum(A))

### FIXED CODE ###

import heapq

def f(x):
    return -int(x)

N, M = map(int, input().split())
A = list(map(f, input().split()))

A.sort()

for _ in range(M):
    a = A[0]
    heapq.heappop(A)
    heapq.heappush(A, -((-a)//2))
    
print(-sum(A))
### BUGGY CODE ###

N, W = list(map(lambda x: int(x), input().split()))
w = []
v = []
for i in range(N):
  line = input().split()
  w.append(int(line[0]))
  v.append(int(line[1]))
  
inf = 10**10
M = sum(v)+1
dp = [ [0] + [inf]*(M-1) for i in range(N) ]
dp[0][v[0]] = w[0] #最初の行

for i in range(1, N):
  for val in range(1, M):
    if val-v[i]>=0:
      dp[i][val] = dp[i-1][val-v[i]] + w[i]
    dp[i][val] = min(dp[i][val], dp[i-1][val])
    
#許されるvの最大値を見つける
for val in reversed(range(M)):
  if dp[N-1][val]<=W:
    print(val)
    break


### FIXED CODE ###

N, W = list(map(lambda x: int(x), input().split()))
w = []
v = []
for i in range(N):
  line = input().split()
  w.append(int(line[0]))
  v.append(int(line[1]))
  
inf = 10**10
M = sum(v)+1
dp = [ [0] + [inf]*(M-1) for i in range(N) ]
dp[0][v[0]] = w[0] #最初の行

lim = v[0]+1
for i in range(1, N):
  lim += v[i]
  for val in range(1, lim):
    if val-v[i]>=0:
      dp[i][val] = dp[i-1][val-v[i]] + w[i]
    dp[i][val] = min(dp[i][val], dp[i-1][val])
    
#許されるvの最大値を見つける
for val in reversed(range(M)):
  if dp[N-1][val]<=W:
    print(val)
    break
### BUGGY CODE ###

N, K = map(int, input().split())
ps = list(map(int, input().split()))
E = lambda x: x if x==1 else (x+1)*(x/2)/x
ans = (0,0)
for i in range(N-(K-1)):
  s = sum(ps[i:i+K])
  ans = (i,s) if ans[1] < s else ans
print(sum(map(E, ps[ans[0]:ans[0]+K])))

### FIXED CODE ###

from itertools import accumulate
N, K = map(int, input().split())
ans = [0] + list(accumulate(map(lambda x: (int(x)+1)/2., input().split())))
print(max([y-x for x,y in zip(ans, ans[K:])]))
### BUGGY CODE ###


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


dp = [10 ** 10] * N
dp = dp + [10 ** 10] * 1000
dp[0] = 0

footing = footing + [0] * 1000
# give
'''
for i in range(N-1):
    for k in range(1, K+1):
        if dp[i+k] > dp[i] + abs(footing[i+k] - footing[i]):
            dp[i+k] = dp[i] + abs(footing[i+k] - footing[i])

print(dp[N-1])
'''
# get
for i in range(1,N):
    for j in range(1,min(K+1, i+1)): 
        if dp[i] > dp[i-j] + abs(footing[i]-footing[i-j]):
            dp[i] = dp[i-j] + abs(footing[i]-footing[i-j]) 

print(dp[N-1])

### FIXED CODE ###

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


dp = [10 ** 10] * N
dp = dp + [10 ** 10] * 1000
dp[0] = 0

footing = footing + [0] * 1000
# give
'''
for i in range(N-1):
    for k in range(1, K+1):
        if dp[i+k] > dp[i] + abs(footing[i+k] - footing[i]):
            dp[i+k] = dp[i] + abs(footing[i+k] - footing[i])

print(dp[N-1])
'''
# get
for i in range(1,N):
    for j in range(1,min(K+1, i+1)): 
        dp[i] = min(dp[i],dp[i-j] + abs(footing[i]-footing[i-j])) 

print(dp[N-1])
### BUGGY CODE ###

N = int(input())

res = 0

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

nums = []
for i in range(N):
    num = p[i]
    nums.append(num)
    flag = True
    for j in nums:
        if num > j:
            flag = False
            break
    if flag == True:
        res += 1

print(res)

### FIXED CODE ###

N = int(input())
res = 0
p = list(map(int, input().split()))
mini = p[0]
for i in range(N):
    mini = min(mini, p[i])
    if mini >= p[i]:
        res += 1    
print(res)
### BUGGY CODE ###

alph="abcdefghijklmnopqrstuvwxyz"
from collections import deque
import sys
input=sys.stdin.readline
moji=deque([])
s=input().rstrip()
for i in range(len(s)):
	for j in range(26):
		if s[i]==alph[j]:
			moji.append(j)
			break
q=int(input())
rev=0
for _ in range(q):
	qw=input().split()
	if qw[0]=="1":
		rev+=1
	else:
		f=qw[1]
		c=qw[2]
		for j in range(26):
			if c==alph[j]:
				x=j
				break
		if f=="1":
			if rev%2==0:
				moji.appendleft(x)
			else:
				moji.append(x)
		else:
			if rev%2==0:
				moji.append(x)
			else:
				moji.appendleft(x)
ans=""
for i in range(len(moji)):
	ans+=alph[moji[i]]
if rev%2==0:
	print(ans)
else:
	print(ans[::-1])

### FIXED CODE ###

alph="abcdefghijklmnopqrstuvwxyz"
from collections import deque
import sys
input=sys.stdin.readline
moji=deque([])
s=input().rstrip()
for i in range(len(s)):
	for j in range(26):
		if s[i]==alph[j]:
			moji.append(j)
			break
q=int(input())
rev=0
for _ in range(q):
	qw=input().split()
	if qw[0]=="1":
		rev+=1
	else:
		f=qw[1]
		c=qw[2]
		for j in range(26):
			if c==alph[j]:
				x=j
				break
		if f=="1":
			if rev%2==0:
				moji.appendleft(x)
			else:
				moji.append(x)
		else:
			if rev%2==0:
				moji.append(x)
			else:
				moji.appendleft(x)
ans=""
r=[]
for i in range(len(moji)):
	r.append(moji.popleft())
for i in range(len(r)):
	ans+=alph[r[i]]
if rev%2==0:
	print(ans)
else:
	print(ans[::-1])
### BUGGY CODE ###

n,s=map(int,input().split())
a=list(map(int,input().split()))
mod=998244353

dp=[[0]*s for _ in range(n)]

for i in range(n):
    if a[i]<=s:
        dp[i][a[i]-1]=2**i
    for j in range(s):
        if i>0:
            dp[i][j]+=dp[i-1][j]*2
            if j+a[i]<s:
                dp[i][j+a[i]]+=dp[i-1][j]
            
print(dp[n-1][s-1]%mod)

### FIXED CODE ###

n,s=map(int,input().split())
a=list(map(int,input().split()))
mod=998244353

dp=[[0]*s for _ in range(n)]    
tmp=1
for i in range(n):
    if a[i]<=s:
        dp[i][a[i]-1]=tmp
    for j in range(s):
        if i>0:
            dp[i][j]+=dp[i-1][j]*2
            dp[i][j]%=mod
            if j+a[i]<s:
                dp[i][j+a[i]]+=dp[i-1][j]
                dp[i][j+a[i]]%=mod
    tmp*=2
    tmp%=mod
            
print(dp[n-1][s-1])
### BUGGY CODE ###

a_0b =0
A, B = map(int, input().split())
for i in range(A, B+1):
    a_0b = i ^ a_0b
print(a_0b)

### FIXED CODE ###

a = 0
A, B = map(int, input().split())
c = (B + 1 - A) // 2
d = (B + 1 - A) % 2
if d == 0 and A % 2 == 0:
    if c % 2 == 0:
        a = 0
    else:
        a = 1
elif d == 0 and A % 2 != 0:
    if (c-1) % 2 == 0:
        a = A ^ B
    else:
        a = 1 ^ A ^ B
elif d == 1 and A % 2 == 0:
    if c % 2 == 0:
        a = B
    else:
        a = 1 ^ B
elif d == 1 and A % 2 != 0:
    if c % 2 == 0:
        a = A
    else:
        a = 1 ^ A
print(a)
### BUGGY CODE ###

# E
import numpy as np
N, T = map(int, input().split())
# A=cost. B=value
A, B = np.array([input().split() for _ in range(N)], dtype=int).T

weight,value = A, B
# dp[i][w] = i番目までからwを超えないように選んだ時の最大値, まだ最後の食べ物を選んでない
d0 = np.zeros((N,T),int)
# dp[i][w] = i番目までからwを超えないように選んだ時の最大値, もう最後の食べ物を選んだ
d1 = np.zeros((N,T),int)
# 初期値として0番目の商品を加える
d0[0,weight[0]:] = value[0]
d1[0,:] = value[0]

for n in range(1, N):
  for w in range(T):
    if (w >= weight[n]):
      d0[n][w] = max(d0[n-1][w-weight[n]] + value[n], d0[n-1][w])
      d1[n][w] = max(d1[n-1][w-weight[n]] + value[n], d1[n-1][w], d0[n-1][w] + value[n])
    else:
      d0[n][w] = d0[n-1][w]
      d1[n][w] = max(d1[n-1][w], d0[n-1][w] + value[n])

print(d1[-1,-1])

### FIXED CODE ###

# E
import numpy as np
N, T = map(int, input().split())
# A=cost. B=value
A, B = np.array([input().split() for _ in range(N)], dtype=int).T

weight,value = A, B
# dp[i][w] = i番目までからwを超えないように選んだ時の最大値, まだ最後の食べ物を選んでない
d0 = np.zeros((N,T),int)
# dp[i][w] = i番目までからwを超えないように選んだ時の最大値, もう最後の食べ物を選んだ
d1 = np.zeros((N,T),int)
# 初期値として0番目の商品を加える
d0[0,weight[0]:] = value[0]
d1[0,:] = value[0]

for n in range(1, N):
  w = weight[n]
  # w < weight[n]
  d0[n][:w] = d0[n-1][:w]
  d1[n][:w] = np.fmax(d1[n-1][:w], d0[n-1][:w] + value[n])
  # w >= weight[n]
  d0[n][w:] = np.fmax(d0[n-1][:-w] + value[n], d0[n-1][w:])
  d1[n][w:] = np.fmax(np.fmax(d1[n-1][:-w] + value[n], d1[n-1][w:]), d0[n-1][w:] + value[n])

print(d1[-1,-1])
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
b = []
c = [0 for _ in range(n)]

def make_divisors(n):
	lower_divisors , upper_divisors = [], []
	i = 1
	while i*i <= n:
		if n % i == 0:
			lower_divisors.append(i)
			if i != n // i:
				upper_divisors.append(n//i)
		i += 1
	return lower_divisors + upper_divisors[::-1]

#半分より上は, すべてa通り.
for i in range(1,n+1)[::-1]:
	if c[i-1] % 2 != a[i-1]:
		b.append(i)
		for j in make_divisors(i):
			c[j-1] += 1
print(len(b))
print(" ".join(list(map(str, b))))

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
b = []
c = [0 for _ in range(n)]

def make_divisors(n):
	lower_divisors , upper_divisors = [], []
	i = 1
	while i*i <= n:
		if n % i == 0:
			lower_divisors.append(i)
			if i != n // i:
				upper_divisors.append(n//i)
		i += 1
	return lower_divisors + upper_divisors[::-1]

#半分より上は, すべてa通り.
for i in range(1,n+1)[::-1]:
	if c[i-1] % 2 != a[i-1]:
		b.append(i)
		for j in make_divisors(i):
			c[j-1] += 1
print(len(b))
print(" ".join(list(map(str, b))))
### BUGGY CODE ###

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

def calc(n):
  return (n+1)/2

max_e=0
for i in range(N-(K-1)):
  v=p[i:K+i]
  #print(v)
  e=list(map(calc, v))
  #print(e)
  e=sum(e)

  if max_e<e:
    max_e=e

print(max_e)

### FIXED CODE ###

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

p = [(n+1)/2 for n in p]
import numpy as np
s = np.cumsum(p)

e=s[K-1]
max_e=e
for i in range(1,N-K):
  e=s[i+K]-s[i]
  max_e = max(max_e, e)
    
print(max_e)
### BUGGY CODE ###

# from operator import mul
# from functools import reduce

n=int(input())
a=list(map(int,input().split()))
limit=10**18

ans = 1
# ans = reduce(mul, a) #=> 1320

for i in range(n):
  ans *= a[i]
  if a[i] == 0:
    break

if ans > limit:
  print(-1)
else:
  print(ans)


### FIXED CODE ###

# from operator import mul
# from functools import reduce

n=int(input())
a=list(map(int, input().split()))
# limit=10**18

# if 0 in a:
#     print(0)
#     exit()

ans = 1
# ans = reduce(mul, a) #=> 1320

for i in range(n):
  ans *= a[i]
  if ans > 10 ** 18:
  # if a[i] == 0:
  #   break
  # elif (ans*a[i]) > limit:
    ans = -1
    break

for i in range(n):
  if a[i] == 0:
      ans = 0

# if ans > limit:
#   print(-1)
# else:
print(ans)
### BUGGY CODE ###

N, M = map(int,input().split())
j=1
for i in range(1, M//N + 1):
    if M%i==0:
        j=i
print(j)


### FIXED CODE ###

import math
N, M = map(int,input().split())
j=1
for i in range(1, int(math.sqrt(M))+2):
    if M%i==0:
        if i <= M//N and j < i:
            j=i
        if M//i <= M//N and j < M//i:
            j=M//i
print(j)
### BUGGY CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))

a.sort()
p = []
for i in range(n):
   for j in range(i+1, n):
      p.append(a[i]*a[j])

p.sort()
print(p[k-1])


### FIXED CODE ###

import numpy as np

n, k = map(int, input().split())
a = list(map(int, input().split()))

a = np.array(a)
a.sort()

nega = a[a<0]
zero = a[a==0]
posi = a[a>0]

l = -10**18-1
r = 10**18+1
while r - l > 1:
   mid = (r+l)//2
   cnt = 0
   if mid >= 0:
      cnt += len(zero)*n
   cnt += a.searchsorted(mid//posi, side='right').sum()
   cnt += (n - a.searchsorted(-(-mid//nega), side='left')).sum()
   cnt -= np.count_nonzero(a*a <= mid)
   cnt //=2
   if cnt >= k:
      r = mid
   else:
      l= mid

print(r)
### BUGGY CODE ###

X,Y,A,B,C=(int(x) for x in input().split())
ps = sorted([int(x) for x in input().split()],reverse=True)
qs = sorted([int(x) for x in input().split()],reverse=True)
rs = sorted([int(x) for x in input().split()],reverse=True)
sta = sorted(ps[:X] + qs[:Y])
for i in range(C):
  if rs[i]> min(sta):
    sta[i]=rs[i]
  else:
    break
print(sum(sta))

### FIXED CODE ###

X,Y,A,B,C=(int(x) for x in input().split())
ps = sorted([int(x) for x in input().split()],reverse=True)
qs = sorted([int(x) for x in input().split()],reverse=True)
rs = sorted([int(x) for x in input().split()],reverse=True)
sta = sorted(ps[:X] + qs[:Y])
res = sum(sta)
for i in range(C):
  a = rs[i]
  s = sta[i]
  if a> s:
    res += a-s
  else:
    break
print(res)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(2 * 10**6)


def inpl():
    return list(map(int, input().split()))


def dfs(v=0, c=0):
    visited[v] = True
    c += counter.get(v, 0)
    ans[v] = c
    for nv in edge[v]:
        if visited[nv] is True:
            continue
        dfs(nv, c)
    return


N, Q = inpl()

edge = [[] for i in range(N)]
for i in range(N - 1):
    a, b = inpl()
    edge[a - 1].append(b - 1)
    edge[b - 1].append(a - 1)

counter = {}
for i in range(Q):
    p, q = inpl()
    counter[p - 1] = counter.get(p - 1, 0) + q

ans = [0 for i in range(N)]
visited = [False for i in range(N)]

dfs()

print(" ".join(list(map(str, ans))))


### FIXED CODE ###

import sys
from collections import deque
sys.setrecursionlimit(2 * 10**6)


def inpl():
    return list(map(int, input().split()))


def bfs():
    visited[0] = True
    ans[0] = counter[0]
    deq = deque()
    deq.append(0)
    while deq:
        v = deq.popleft()
        for nv in edge[v]:
            if visited[nv] is True:
                continue
            visited[nv] = True
            ans[nv] = ans[v] + counter[nv]
            deq.append(nv)


N, Q = inpl()

edge = [[] for i in range(N)]
for i in range(N - 1):
    a, b = inpl()
    edge[a - 1].append(b - 1)
    edge[b - 1].append(a - 1)

counter = {k: 0 for k in range(N)}
for i in range(Q):
    p, q = inpl()
    counter[p - 1] = counter.get(p - 1, 0) + q

ans = [0 for i in range(N)]
visited = [False for i in range(N)]

bfs()

print(" ".join(list(map(str, ans))))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10000)
def resolve():
    s = input()
    K = int(input())
    mem = []
    for i in range(1, len(s)+1): # window size
        for j in range(len(s)): # window starts at
            subs = s[j:j+i]
            if subs not in mem:
                mem.append(subs)
    mem.sort()
    # print(mem)
    print(mem[K-1])


if '__main__' == __name__:
    resolve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10000)
def resolve():
    s = input()
    K = int(input())
    mem = []
    for i in range(1, K+1): # window size
        for j in range(len(s)): # window starts at
            subs = s[j:j+i]
            if subs not in mem:
                mem.append(subs)
    mem.sort()
    # print(mem)
    print(mem[K-1])
    
    
if '__main__' == __name__:
    resolve()
### BUGGY CODE ###

from collections import deque
H,W=map(int,input().split())
stack=deque()
c=[input() for i in range(H)]
ans=0
for i in range(H):
    for j in range(W):
        if c[i][j]=="#":
            stack.append((i,j))
reached=[[0]*W for i in range(H)]
dydx=[(1,0),(-1,0),(0,1),(0,-1)]
while(stack):
    Y,X=stack.popleft()
    for dy,dx in dydx:
        y=Y+dy
        x=X+dx
        if y<0 or y>=H or x<0 or x>=W or c[y][x]=="#":
            continue
        if reached[y][x]!=0:
            continue
        stack.append((y,x))
        reached[y][x]=reached[Y][X]+1
for i in range(H):
    for j in range(W):
        ans=max(ans,reached[i][j])
print(ans)


### FIXED CODE ###

from collections import deque
H,W=map(int,input().split())
stack=deque()
c=[input() for i in range(H)]
ans=0
reached=[[-1]*W for i in range(H)]
for i in range(H):
    for j in range(W):
        if c[i][j]=="#":
            stack.append((i,j))
            reached[i][j]=0
dydx=[(1,0),(-1,0),(0,1),(0,-1)]
while(stack):
    Y,X=stack.popleft()
    for dy,dx in dydx:
        y=Y+dy
        x=X+dx
        if y<0 or y>=H or x<0 or x>=W or c[y][x]=="#":
            continue
        if reached[y][x]!=-1:
            continue
        stack.append((y,x))
        reached[y][x]=reached[Y][X]+1
        ans=max(ans,reached[y][x])
print(ans)
### BUGGY CODE ###

def main():
    n = int(input())
    a = list(map(int, input().split()))
    q = int(input())
    for _ in range(q):
        l = []
        b, c = map(int, input().split())
        for i in a:
            l.append(c) if i == b else l.append(i)
        print(sum(l))

        a = l[:]


if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import Counter


def main():
    n = int(input())
    a = list(map(int, input().split()))
    cnt = Counter(a)
    q = int(input())
    s = sum(a)
    for _ in range(q):
        b, c = map(int, input().split())
        s -= cnt[b]*b

        s += cnt[b]*c
        cnt[c] += cnt[b]
        cnt[b] = 0
        print(s)

if __name__ == "__main__":
    main()
### BUGGY CODE ###

n,k = map(int,input().split())
H = list(map(int,input().split()))
dp = [0]*n

if n <= k:
    print(abs(H[0]-H[-1]))
else:
    for i in range(1,n):
        if i <= k:
            dp[i] = abs(H[i]-H[0])
        else:
            res = abs(H[i]-H[i-k])+dp[i-k]
            for j in range(1,k):
                res = min(res,abs(H[i]-H[i-j])+dp[i-j])
            dp[i] = res
    print(dp[n-1]) 

### FIXED CODE ###

n,k = map(int,input().split())
H = list(map(int,input().split()))
dp = [0]*n

if n <= k:
    print(abs(H[0]-H[-1]))
else:
    for i in range(1,k+1):
        dp[i] = abs(H[i]-H[0])
    for i in range(k+1,n):
        res = abs(H[i]-H[i-k])+dp[i-k]
        for j in range(1,k):
            res = min(res,abs(H[i]-H[i-j])+dp[i-j])
        dp[i] = res
    print(dp[n-1])