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

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import deque

N,Q = map(int,readline().split())
ki = [list(map(int,readline().split())) for i in range(N-1)]
co = [list(map(int,readline().split())) for i in range(Q)]
 
ki.sort(key=lambda x: x[1])

kid = deque(ki)
ver = [0 for i in range(N)]
check = [False for i in range(N)]
 
for c in co:
    ver[c[0]-1] += c[1]

check[0] = True

kid2 = deque()

while len(kid) != 0:
    k = kid.popleft()
    if check[k[0]-1] == True:
        ver[k[1]-1] += ver[k[0]-1]
        check[k[1]-1] = True
    elif check[k[1]-1] == True:
        ver[k[0]-1] += ver[k[1]-1]
        check[k[0]-1] = True
    else:
        kid2.append(k)

while len(kid2) != 0:
    k = kid2.pop()
    if check[k[0]-1] == True:
        ver[k[1]-1] += ver[k[0]-1]
        check[k[1]-1] = True
    elif check[k[1]-1] == True:
        ver[k[0]-1] += ver[k[1]-1]
        check[k[0]-1] = True
    else:
        kid2.appendleft(k)


print(' '.join(map(str,ver)))


### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import deque

N,Q = map(int,readline().split())
ki = []
for i in range(N-1):
    ki.append(list(map(int,readline().split())))
co = []
for i in range(Q):
    co.append(list(map(int,readline().split())))
 
ki.sort(key=lambda x: x[1])

kid = deque(ki)
ver = []
check = []
for i in range(N):
    ver.append(0)
    check.append(False)
 
for c in co:
    ver[c[0]-1] += c[1]

check[0] = True

kid2 = deque()

while len(kid) != 0:
    k = kid.popleft()
    if check[k[0]-1] == True:
        ver[k[1]-1] += ver[k[0]-1]
        check[k[1]-1] = True
    elif check[k[1]-1] == True:
        ver[k[0]-1] += ver[k[1]-1]
        check[k[0]-1] = True
    else:
        kid2.append(k)

while len(kid2) != 0:
    k = kid2.pop()
    if check[k[0]-1] == True:
        ver[k[1]-1] += ver[k[0]-1]
        check[k[1]-1] = True
    elif check[k[1]-1] == True:
        ver[k[0]-1] += ver[k[1]-1]
        check[k[0]-1] = True
    else:
        kid2.appendleft(k)


print(' '.join(map(str,ver)))
### BUGGY CODE ###

n,q=map(int,input().split())
s=input()
for i in range(q):
  l,r=map(int,input().split())
  print(s[l-1:r].count('AC'))

### FIXED CODE ###

n,q=map(int,input().split())
s=input()
lr=[list(map(int,input().split())) for i in range(q)]
data=[0]*(n+1)
if s[0]=='A' and s[1]=='C':
  data[1]=1
for i in range(1,n-1):
  if s[i]=='A' and s[i+1]=='C':
    data[i+1]+=1
  data[i+1]+=data[i]
data[n]=data[n-1]
for i in range(q):
  print(data[lr[i][1]-1]-data[lr[i][0]-1])
### BUGGY CODE ###

k,n = map(int, input().split())
res = 0
for i in range(k+1):
    for j in range(k+1):
        for h in range(k+1):
            if i+j+h==n:
                res +=1
                x =[i,j,h]
print(res)

### FIXED CODE ###

k,n = map(int, input().split())
res = 0
for i in range(k+1):
    for j in range(k+1):
        if i + j > n : break
        h = n - i - j
        if h <= k:
            res +=1
print(res)
### BUGGY CODE ###

from collections import deque
d = deque()
length = 0
for x in input():
    d.append(x)
    length += 1
Q = int(input())
f = 0
for _ in range(Q):
    l = list(input().split())
    if l[0] == '1':
        f ^= 1
    else:
        length += 1
        if f == 0: 
            if l[1] == '2': d.append(l[2])
            else: d.appendleft(l[2])
        else:
            if l[1] == '2': d.appendleft(l[2])
            else: d.append(l[2])
ans = ''
for x in range(length):
    ans += d.pop()
if f == 0:
    print(ans[::-1])    
else:
    print(ans)


### FIXED CODE ###

from collections import deque
d = deque()
length = 0
for x in input():
    d.append(x)
    length += 1
Q = int(input())
f = 0
for _ in range(Q):
    l = list(input().split())
    if l[0] == '1':
        f ^= 1
    else:
        length += 1
        if f == 0: 
            if l[1] == '2': d.append(l[2])
            else: d.appendleft(l[2])
        else:
            if l[1] == '2': d.appendleft(l[2])
            else: d.append(l[2])
ans = ''
for x in range(length):
    ans += d.pop()
if f == 0:
    print(ans[::-1])    
else:
    print(ans)
### BUGGY CODE ###

# coding: utf-8
# Your code here!

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors
    
    
kosuu = int(input())
nums = list(map(int,input().split()))

temp_arr=[]
for temp in nums:
    temp_arr.append(make_divisors(temp))
    

temp_arr2 = sum(temp_arr,[])
temp_arr2.sort(reverse=True)
for temp in temp_arr2:
    suuzi = temp_arr2.count(temp)
    if suuzi == kosuu -1 or suuzi == kosuu:
        print(temp)
        break

### FIXED CODE ###

def gcd(a,b):
    if ( b==0 ):
        return a
    else:
        return (gcd(b, a%b))

kosuu = int(input())
nums = list(map(int,input().split()))

L = []
R = []
for temp in range(kosuu-1):
    if temp == 0:
        L.append(nums[0])
    else:
        L.append(gcd(L[temp-1],nums[temp]))

for temp in range(kosuu-1):
    if temp == 0:
        R.append(nums[kosuu-1])
    else:
        R.append(gcd(R[temp-1],nums[len(nums)-temp-1]))

saidai=[]
for i in range(kosuu):
    if i == 0:
        saidai.append(L[-1])
    elif i == kosuu-1:
        saidai.append(R[-1])
    else:
        saidai.append(gcd(L[i-1],R[-1-i]))

print(max(saidai))
### BUGGY CODE ###

n = int(input())
a = [i for i in input().split()]
outStr = []
if n % 2 == 0:
    for i in range(n):
        # print("i:{} outStr:{}".format(i, outStr))
        if i % 2 == 1:
            outStr = [a[i]] + outStr
        else:
            outStr.append(a[i])
        # print("i:{} outStr:{}\n".format(i, outStr))
    print(" ".join(outStr))
else:
    for i in range(n):
        if i % 2 == 0:
            outStr = [a[i]] + outStr
        else:
            outStr.append(a[i])
    print(" ".join(outStr))

### FIXED CODE ###

n = int(input())
a = [i for i in input().split()]
outStr = []
if n % 2 == 0:
    for i in reversed(range(int(n/2))):
        outStr += [a[int(i * 2)+1]]
    for i in range(int(n/2)):
        outStr += [a[int(i*2)]]
    print(" ".join(outStr))
else:
    for i in reversed(range(int(n/2)+1)):
        outStr += [a[int(i*2)]]
    for i in range(int(n/2)):
        outStr += [a[int(i*2)+1]]
    print(" ".join(outStr))
### BUGGY CODE ###

import math
b=[]
b.append(1)
b.append(2)
count=1
s=0
while s<30:
    try:
        x=int(input())
        if x>b[count]:
            for i in range(b[count]+1,x+1):
                count1=0
                
                for j in range(2,int(math.sqrt(i))+1):
                    if i%j==0:
                        count1=1
                        break
                if count1==0:
                    count+=1
                    b.append(i)
            print(count)
            print(b)
        else:
            for i in range(count+1):
                if b[i]>x:
                    print(i-1)
                    break
                elif b[i]==x:
                    print(i)
                    break
        s+=1
    except EOFError:
        break

### FIXED CODE ###

str1=[0 for i in range(10**6)]
str1[0]=1
str1[1]=1
for i in range(2,(10**6)):
    if str1[i]==0:
        for j in range(2,(10**6)):
            if i*j>=len(str1):
                break
            else:
                str1[i*j]=1
            
while 1 :
    try:
        x=int(input())
        count=0
        for i in range(1,x+1):
            if str1[i]==0:
                count+=1
        print(count)
        
    except EOFError:
        break
### BUGGY CODE ###

S = int(input())

str_S = str(S)
count = 0

for i in range(len(str_S)-3):
    for j in range(i+4, len(str_S)+1):
        partial = int(str_S[i:j])
        if partial % 2019 == 0:
            count += 1

print(count)

### FIXED CODE ###

s = input()[::-1]

counts = [0] * 2019
counts[0] = 1

num, d = 0, 1

for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d%= 2019
    counts[num] += 1

ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2

print(ans)
### BUGGY CODE ###

N = int(input())
list = list(map(int,input().split()))
ans = 1
for i in list:
  ans *= i
if ans > 10**18:
  ans = -1
print(ans)

### FIXED CODE ###

import numpy as np
N = int(input())
list = list(map(int,input().split()))
ans = np.prod(list)
if ans > 10**18 or ans == 0:
  ans = -1
if 0 in list:
  ans = 0
print(ans)
### BUGGY CODE ###

A, B, C, K = map(int, input().split())
lst = []
sum = 0

for i in range(A):
    lst.append(1)
for j in range(B):
    lst.append(0)
for s in range(C):
    lst.append(-1)

for t in range(K):
    sum += lst[t]

print(sum)

### FIXED CODE ###

A, B, C, K = map(int, input().split())
lst = []
sum = 0
if A <= K:
    sum += 1 * A
else:
    sum += 1 * K

k = K - (A + B)

if (C <= k) and (k > 0):
    sum += -1 * C
elif (C > k) and k > 0:
    sum += -1 * k

print(sum)
### BUGGY CODE ###

#-------------------------------------------------------------------
import sys
def p(*_a):
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
#-------------------------------------------------------------------
from bisect import bisect_right as br
from bisect import bisect_left  as bl
from bisect import insort_right as ir
from bisect import insort_left  as il
#-------------------------------------------------------------------

N, M = map(int, input().split())		# 5 7 2
A = sorted(list( map(int, input().split()) ))

p("A ",A)

if N==1:
	print( int(A[0]/(2**M)) )
	exit(0)


while M>0:
	a = A.pop(-1)
	if int(a)==1: break

	a/=2
	M-=1
	
	b = A[-1]
	while a >= b:
		a/=2
		M-=1
		
	ir(A,a)
	
	p("a,b,A ",a,b,A)

ans=0
for a in A:
	ans += int(a)

print(ans)


### FIXED CODE ###

#-------------------------------------------------------------------
import sys
def p(*_a):
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
#-------------------------------------------------------------------
from heapq import heappush
from heapq import heappop
from heapq import heappushpop
from heapq import heapify
from heapq import nlargest
from heapq import nsmallest
#-------------------------------------------------------------------

N, M = map(int, input().split())		# 5 7 2
#A = list( map(int, input().split()) )
H = list( -int(i) for i in input().split() )

#p("A ",A)
p("H ",H)

heapify(H)

p("H ",H)

for _ in range(M):
	h = heappop(H)//(-2)
	heappush(H,-h)
	
	#p("h,H ",h,H)


print(-sum(H))
### BUGGY CODE ###

import networkx as nx

def main():
  N,M=map(int,input().split())
  S = [list(input()) for _ in range(N)]

  if N == M == 1:
    print(0)
    print(S[0][0])
    exit()

  index = lambda i,j: i*M+j

  G=nx.DiGraph()
  G.add_node('source')
  G.add_node('sink')
  dx,dy=(1,0),(0,1)
  for i in range(N):
    for j in range(M):
      if S[i][j]=='#':continue
      if (i+j) %2:
        G.add_edge(index(i,j),'sink',capacity=1)
      else:
        G.add_edge('source',index(i,j),capacity=1)
      for k in range(2):
        v1,v2 = index(i,j),index(i+dx[k],j+dy[k])
        if not (0<=i+dx[k]<N and 0<=j+dy[k]<M):
          continue
        if S[i+dx[k]][j+dy[k]] == '#': continue
        if (i+j) % 2:
          G.add_edge(v2,v1,capacity=1)
        else:
          G.add_edge(v1,v2,capacity=1)
         
  flow_value, flow_dict = nx.maximum_flow(G, "source", "sink")

  for v1 in flow_dict.keys():
    if v1 in ('sink','source'):continue
    for v2 in flow_dict[v1].keys():
      if v2 in ('sink','source'):continue
      if flow_dict[v1][v2]:
        i1,j1 = divmod(v1,M)
        i2,j2 = divmod(v2,M)
        if i1 > i2 or j1 > j2:
          (i1,j1),(i2,j2) = (i2,j2),(i1,j1)
        if i1 < i2:
          S[i1][j1] = 'v'
          S[i2][j2] = '^'
        else:
          S[i1][j1] = '>'
          S[i2][j2] = '<'

  print(flow_value)
  for i in range(N):
    print(''.join(S[i]))
    
if __name__ == "__main__":
  main()

### FIXED CODE ###

import networkx as nx

def main():
  N,M=map(int,input().split())
  S = [list(input()) for _ in range(N)]

  if N == M == 1:
    print(0)
    print(S[0][0])
    exit()

  index = lambda i,j: i*M+j

  G=nx.Graph()
  dx,dy=(1,0),(0,1)
  E = []
  n1,n2 = [],[]
  for i in range(N):
    for j in range(M):
      if S[i][j]=='#':continue
      if (i+j)%2:
        n1.append(index(i,j))
      else:
        n2.append(index(i,j))
      for k in range(2):
        v1,v2 = index(i,j),index(i+dx[k],j+dy[k])
        if not (0<=i+dx[k]<N and 0<=j+dy[k]<M):
          continue
        if S[i+dx[k]][j+dy[k]] == '#': continue
        if (i+j) % 2:
          E.append((v2,v1))
        else:
          E.append((v1,v2))
     
  G.add_nodes_from(n1, bipartite=0)
  G.add_nodes_from(n2, bipartite=1)
  G.add_edges_from(E)
  u = [n for n in G.nodes if G.nodes[n]['bipartite'] == 0]
  match = nx.bipartite.maximum_matching(G, top_nodes=u)
  match = {v:match[v] for v in match.keys() if v < match[v]}
 
  for v in match.keys():
    i1,j1 = divmod(v,M)
    i2,j2 = divmod(match[v],M)
    if i1 > i2 or j1 > j2:
      (i1,j1),(i2,j2) = (i2,j2),(i1,j1)
    if i1 < i2:
      S[i1][j1] = 'v'
      S[i2][j2] = '^'
    else:
      S[i1][j1] = '>'
      S[i2][j2] = '<'

  print(len(match))
  for i in range(N):
    print(''.join(S[i]))
    
if __name__ == "__main__":
  main()
### BUGGY CODE ###

import numpy as np
a = list(map(int,input().split()))
N = a[0]
K = a[1]
b = list(map(int,input().split()))
li = list(set(b))
c = np.array(b)
d = np.array([])
h = len(li) -K
Num = 0
if K >= len(li):
  print(0)
  exit()
for i in li :
  ind = np.take(c,np.where( c== i),axis = 0)
  d = np.append(d,ind.shape[1])
d = np.sort(d)
for i in range(h):
  Num += d[i]
print(int(Num))

### FIXED CODE ###

import numpy as np
from collections import Counter
import collections
a = list(map(int,input().split()))
N = a[0]
K = a[1]
d = np.array([])
b = list(map(int,input().split()))
li = list(set(b))
c = np.array(b)
l = Counter(b)
h = len(li) -K
Num = 0
if K >= len(li):
  print(0)
  exit()
d = np.append(d,list(l.values()))
d = np.sort(d)
for i in range(h):
  Num += d[i]
print(int(Num))
### BUGGY CODE ###

k=int(input())
n='7'
cnt=1
if k%2==0 or k%5==0:
  print(-1)
  exit()
while True:
  if int(n)%k!=0:
    n+='7'
    cnt+=1
  else:
    print(cnt)
    exit()

### FIXED CODE ###

k=int(input())
n='7'
cnt=1
if k%2==0 or k%5==0:
  print(-1)
  exit()
while True:
  if int(n)%k!=0:
    n=int(n)%k
    n=str(n)+'7'
    cnt+=1
  else:
    print(cnt)
    exit()
### BUGGY CODE ###

N = int(input())

ans = 0
for i in range(N):
  ans += i%(i+1)
  if i == N-1:
    ans += i%1
    
print(ans)

### FIXED CODE ###

N = int(input())

ans = N*(N-1)//2

print(ans)
### BUGGY CODE ###

import numpy as np
N, K = map(int, input().split())
A = list(map(int, input().split()))
sumlist = [sum(A[j:j+N-i]) for i in range(N) for j in range(i+1)]
sumlist.sort(reverse=True)
sumlist = np.array(sumlist)
ans = sumlist[0]
for i in range(40, -1, -1):
    tmp = (ans & (2 ** i)) // (2 ** i)
    if tmp:
        start = i
        break
f = lambda x: (x & onehot) // onehot
ans_list = [0]
for i in range(start, -1, -1):
    onehot = 2 ** i
    tmp = sum(map(f, sumlist))
    if tmp >= K:
        and_result = list(map(f, sumlist))
        and_result = np.array(and_result).astype(np.bool)
        sumlist = sumlist[and_result]
        ans = sumlist[0]
        for j in range(1, K):
            ans = ans & sumlist[j]
        ans_list.append(ans)
print(max(ans_list))


### FIXED CODE ###

from collections import Counter
N, K = map(int, input().split())
A = list(map(int, input().split()))
cusum = [A[0]]
for i in range(1, N):
    cusum += [cusum[-1]+A[i]]
B = []
for i in range(N):
    B += [cusum[i]]
    for j in range(i+1, N):
        B += [cusum[j] - cusum[i]]
max_bit = 43
ans = 0
while max_bit > 0:
    counter = Counter()
    for b in B:
        for i in range(44):
            if b & 1 == 1:
                counter[i] += 1
            b = b >> 1
    for i in range(max_bit, -1, -1):
        if counter[i] >= K:
            filter_bit = 2 ** i
            B = [b for b in B if b & filter_bit == filter_bit]
            max_bit = i-1
            ans += filter_bit
            break
        max_bit = i
print(ans)
### BUGGY CODE ###

N=int(input())
d=list(map(int, input().split()))
C=N//2
for x in range(0,N):
    for y in range(0,N-1):
        if d[y]<d[y+1]:
            t=d[y]
            d[y]=d[y+1]
            d[y+1]=t
    N=N-1
if d[C]==d[C-1]:
    print(0)
else:
    print(d[C-1]-d[C])


### FIXED CODE ###

N=int(input())
d=list(map(int, input().split()))
C=N//2
d.sort()
if d[C]==d[C-1]:
    print(0)
else:
    print(d[C]-d[C-1])
### BUGGY CODE ###

N = int(input())
p = 1

for i in range(N):
    p = p * (i+1)
p = p % (10 ** 9 +7)
print(p)

### FIXED CODE ###

N = int(input())
p = 1
for i in range(N):
    p = p * (i+1)
    p = p % (10 ** 9 +7)
print(p)
### BUGGY CODE ###

n = int(input())
p = 1
for i in range(1, n+1):
    p *= i

print(p % (10**9+7))

### FIXED CODE ###

n = int(input())
p = 1

for i in range(1, n+1):
    p = p * i % 1000000007

print(p)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
 
a = sorted(a)
w = 0
while True:
    h = 1
    cn = 0
    while True:
        if w + h == len(a):
            '''
            print(a)
            '''
            if cn == 1:
                del a[w]
                w -= 1
            break
        if a[w] == a[w+h]:
            cn =1
        if a[w+h] % a[w] == 0:
            '''
            print(h)
            '''
            del a[w+h]
        else:
            '''
            print(a[w+h], h, w, a)
            '''
            h += 1
    w += 1
    if w == len(a):
        print(len(a))
        exit()

### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
c = Counter(a)
prime = [True] * (10 ** 6 + 10)

b = sorted(set(a))

for i in b:
    num = i * 2
    while True:
        if num >= 10 ** 6 + 1:
            break
        prime[num] = False
        num += i

ans = 0
for s in a:
    if prime[s] == True and c[s] == 1:
        ans += 1

print(ans)
### BUGGY CODE ###

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

for i in a[:k]:
    pre *= i
    
for i in range(k,n):
    now = pre * a[i] // a[i-k]
    
    if pre < now:
        print("Yes")
    
    else:
        print("No")
        
    pre = now

### FIXED CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
    
for i in range(k,n):
    if a[i-k] < a[i]:
        print("Yes")
        
    else:
        print("No")
### BUGGY CODE ###

mod = 10**9+7

s = input()
n = len(s)

dp = [0]*13
dp[0] = 1

for i in range(n):
  dp2 = [0]*13  
  for j in range(10):
    if s[i] == '?' or s[i] == str(j):
      for k in range(13):
        dp2[(k*10 + j)%13] += dp[k]
        dp2[(k*10 + j)%13] %= mod
        
  dp = dp2

print(dp[5])

### FIXED CODE ###

mod = 10**9+7

s = input()
n = len(s)

dp = [0]*13
dp[0] = 1

for i in range(n):
  dp2 = [0]*13  
  for j in range(10):
    if s[i] == '?' or s[i] == str(j):
      for k in range(13):
        dp2[(k*10 + j)%13] += dp[k]
        dp2[(k*10 + j)%13] %= mod
        
  dp = dp2

print(dp[5])
### BUGGY CODE ###

import numpy as np
import math
N, D, A = map(int, input().split())
xh = np.array(sorted([list(map(int, input().split())) for _ in range(N)]), dtype=np.int32)
b = 0
while 1:
  if all(xh[:, 1]<=0):
    break
  x, h = xh[0]
  if h<=0:
    continue
  r = min(x+2*D, xh[-1, 0])
  times = math.ceil(h/A)
  xh[xh[:, 0]<=r] -= times*A
  xh = xh[1:]
  b += times
print(b)

### FIXED CODE ###

from bisect import bisect_right

N, D, A = map(int, input().split())
xh = sorted([list(map(int, input().split())) for _ in range(N)])
ds = [0]*(N+2)
b = 0
for i, (x, h) in enumerate(xh, 1):
  ds[i] += ds[i-1]
  d = ds[i]
  if d>=h:
    continue
  h -= d
  times = h//A if h%A==0 else h//A+1
  ds[i] += times*A
  ds[bisect_right(xh, [x+2*D, float('inf')])+1] -= times*A
  b += times
print(b)
### BUGGY CODE ###

n,m,k = map(int, input().split())

a = list(map(int, input().split()))
b = list(map(int, input().split()))

aa = [0]*(n+1)
bb = [0]*(m+1)

for i in range(n):
    aa[i+1] = a[i] + aa[i]

for i in range(m):
    bb[i+1] = b[i] + bb[i]

ans = 0
flag = 0
for i in range(n+1):
    if k - aa[i] < 0:
        flag = 1
        if ans < i-1:
            ans = i-1   
        break
    for j in range(m+1):
        if k - aa[i] - bb[j] < 0:
            flag = 1
            if ans < i + j - 1:
                ans = i + j - 1
            break

if flag == 0:
    print(n+m)
    exit()
print(ans)


### FIXED CODE ###

n,m,k = map(int, input().split())

a = list(map(int, input().split()))
b = list(map(int, input().split()))

aa = [0]
bb = [0]

for i in range(n):
    aa.append(a[i] + aa[i])

for i in range(m):
    bb.append(b[i] + bb[i])

ans = 0
mstart = m
for i in range(n+1):
    if k - aa[i] < 0:
        break
    for j in range(mstart,-1,-1):
        if k - aa[i] - bb[j] >= 0:
            mstart = j
            break
    if ans < i + j :
        ans = i + j 

print(ans)
### BUGGY CODE ###

def main():
    N, K = list(map(int, input().split()))
    H = list(map(int, input().split()))

    INF = 10 ** 10

    dp = [INF for _ in range(N)]

    for i in range(N):
        if i == 0:
            dp[i] = 0
        else:
            for dist in range(1, min(K, i) + 1):
                c = dp[i - dist] + abs(H[i] - H[i - dist])
                if c < dp[i]:
                    dp[i] = c

    print(dp[-1])


if __name__ == '__main__':
    main()


### FIXED CODE ###

import numpy as np


def main():
    N, K = list(map(int, input().split()))
    H = np.array(list(map(int, input().split())))

    INF = float('inf')

    dp = np.array([INF for _ in range(N)])
    dp[0] = 0

    for i in range(1, N):
        max_dist = min(K, i)
        dp[i] = np.min(dp[i - max_dist:i] + np.abs(H[i] - H[i - max_dist:i]))

    print(int(dp[-1]))


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

def getinputdata():

    array_result = []    
    data = input()
    array_result.append(data.split(" "))

    flg = True

    try:
        while flg:

            data = input()

            if(data != ""):
                
                array_result.append(data.split(" "))

                flg = True

            else:

                flg = False
    finally:

        return array_result

arr_data = getinputdata()

x=arr_data[0][0]

while "ST" in x:
    
   x=x.replace("ST","")

print(len(x))


### FIXED CODE ###

from collections import deque
def getinputdata():

    array_result = []    
    data = input()
    array_result.append(data.split(" "))

    flg = True

    try:
        while flg:

            data = input()

            if(data != ""):
                
                array_result.append(data.split(" "))

                flg = True

            else:

                flg = False
    finally:

        return array_result

arr_data = getinputdata()

x=arr_data[0][0]

b = deque([])

for v in x:
    
    if v=="S":
        
        b.appendleft(v)
        
    elif v=="T" and (len(b)==0 or b[0]=="T"):
        
        b.appendleft(v)
        
    else:
            
        b.popleft()
            
print(len(b))
### BUGGY CODE ###

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

cnt = 1
for i in range(1,n):
  if p[i] > p[i-1]:
    continue
  elif min(p[:i+1]) == p[i]:
    cnt += 1
print(cnt)

### FIXED CODE ###

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

min_num = 10**6
cnt = 0
for i in range(n):
  if p[i] < min_num:
    min_num = p[i]
    cnt += 1
print(cnt)