Harryxun/stf_run huggingface dataset:
N, K = map(int, input().split())
T = [[] for i in range(N)]
MOD = 10 ** 9 + 7
for i in range(N - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    T[a].append(b)
    T[b].append(a)


stack = [0]
visited = [0] * N
child_num = [0] * N
while stack:
    n = stack.pop()
    visited[n] = 1
    for to in T[n]:
        if visited[to]:
            continue
        child_num[n] += 1
        stack.append(to)


# 階乗 & 逆元計算
factorial = [1]
inverse = [1]
for i in range(1, K + 1):
    factorial.append(factorial[-1] * i % MOD)
    inverse.append(pow(factorial[-1], MOD - 2, MOD))


# 組み合わせ計算
def nCr(n, r):
    if n < r or r < 0:
        return 0
    elif r == 0:
        return 1
    return factorial[n] * inverse[r] * inverse[n - r] % MOD


ans = K
stack = [0]
visited = [0] * N
while stack:
    n = stack.pop()
    visited[n] = 1

    if n == 0:
        ans = ans * nCr(K - 1, child_num[n]) * factorial[child_num[n]] % MOD
    else:
        ans = ans * nCr(K - 2, child_num[n]) * factorial[child_num[n]] % MOD
    for to in T[n]:
        if visited[to]:
            continue
        stack.append(to)

print(ans)


### FIXED CODE ###

N, K = map(int, input().split())
T = [[] for i in range(N)]
MOD = 10 ** 9 + 7
for i in range(N - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    T[a].append(b)
    T[b].append(a)


stack = [0]
visited = [0] * N
child_num = [0] * N
while stack:
    n = stack.pop()
    visited[n] = 1
    for to in T[n]:
        if visited[to]:
            continue
        child_num[n] += 1
        stack.append(to)


# 階乗 & 逆元計算
factorial = [1]
inverse = [1]
for i in range(1, 10 ** 5 + 1):
    factorial.append(factorial[-1] * i % MOD)
    inverse.append(pow(factorial[-1], MOD - 2, MOD))


# 組み合わせ計算
def nCr(n, r):
    if n < r or r < 0:
        return 0
    elif r == 0:
        return 1
    return factorial[n] * inverse[r] * inverse[n - r] % MOD


ans = K
stack = [0]
visited = [0] * N
while stack:
    n = stack.pop()
    visited[n] = 1

    if n == 0:
        ans = ans * nCr(K - 1, child_num[n]) * factorial[child_num[n]] % MOD
    else:
        ans = ans * nCr(K - 2, child_num[n]) * factorial[child_num[n]] % MOD
    for to in T[n]:
        if visited[to]:
            continue
        stack.append(to)

print(ans % MOD)
from math import floor
A,B,N = map(int,input().split())
if N <= B:
    print(floor(A*N/B)-A*floor(N/B))
else:
    print("1"*"1")
    print(max(floor(A*N/B)-A*floor(N/B),floor(A*(B+1)/B)-A*floor((B+1)/B)))


### FIXED CODE ###

from math import floor
A,B,N = map(int,input().split())
x = min(B-1,N)
print(floor(A*x/B)-A*floor(x/B))
n = int(input())
sp = [list(map(int, input().split())) for _ in range(n)]

sorted(sp, key=lambda x:(x[0],-x[1]))
for i in range(len(sp)):
    print(sp[i])

### FIXED CODE ###

n = int(input())
sp = [list(input().split()) for _ in range(n)]
for i in range(len(sp)):
    sp[i][1] = int(sp[i][1])
d = sorted(sp, key=lambda x:(x[0],-x[1]))
for i in range(len(sp)):
    print(sp.index(d[i])+1)
import math

def avg(L, atLeast, atMost):
	if (L.count(max(L)) >= atLeast):
		print(max(L))
		ways = 0
		for i in range(atLeast, atMost + 1):
			localWays = math.factorial(L.count(max(L))) // math.factorial(i) // math.factorial(L.count(max(L)) - i)
			ways += localWays
		print(ways)
		return
	L.sort(reverse=True)
	last = L[atLeast - 1]
	print(sum(L[:atLeast]) / atLeast)
	print(L.count(last))

[N, atLeast, atMost] = list(map(lambda x: int(x), input().split()))
L = list(map(lambda x: int(x), input().split()))
avg(L, atLeast, atMost)

### FIXED CODE ###

import math

# def comboSum(n, chooseMin, chooseMax):
# 	print(n, chooseMin, chooseMax)
# 	ways = 0
# 	for i in range(chooseMin, chooseMax + 1):
# 		localWays = math.factorial(n) // math.factorial(i) // math.factorial(n - i)
# 		ways += localWays
# 	return ways


def avg(L, atLeast, atMost):
	if (L.count(max(L)) >= atLeast):
		print(max(L))
		ways = 0
		for i in range(atLeast, min(atMost, L.count(max(L))) + 1):
			localWays = math.factorial(L.count(max(L))) // math.factorial(i) // math.factorial(L.count(max(L)) - i)
			ways += localWays
		print(ways)
		return
	L.sort(reverse=True)
	last = L[atLeast - 1]
	print(sum(L[:atLeast]) / atLeast)
	firstIndex = L.index(last)
	# lastIndex = len(L) - (sorted(L).index(last)) - 1
	n = L.count(last)
	i = atLeast - firstIndex
	print(math.factorial(n) // math.factorial(i) // math.factorial(n - i))

[N, atLeast, atMost] = list(map(lambda x: int(x), input().split()))
L = list(map(lambda x: int(x), input().split()))
avg(L, atLeast, atMost)
import sys
input = lambda : sys.stdin.readline().rstrip()

import heapq
h = []
heapq.heapify(h)

n, m, s = list(map(int, input().split()))
a, b = [[None] * m for _ in range(2)]
c, d = [[None] * n for _ in range(2)]

ns = {}
uv2e = {}
for i in range(m):
    u,v,a[i],b[i] = list(map(int, input().split()))
    ns.setdefault(u-1, set())
    ns.setdefault(v-1, set())
    ns[u-1].add(v-1)
    ns[v-1].add(u-1)
    uv2e[u-1,v-1] = i
    uv2e[v-1,u-1] = i
for i in range(n):
    c[i], d[i] = list(map(int, input().split()))

maxs = max(a)*(n-1)
s = min(s, maxs)
state = (0, 0, s) # (距離, ノード, 銀貨枚数)
ans = [[None] * (maxs+1) for _ in range(n)]
ans[0][s] = 0
done = [[None] * (maxs+1) for _ in range(n)]
heapq.heappush(h, state)
count = 0
while h:
    count += 1
    dd, u, ss = heapq.heappop(h)
#     if ans[u][ss] is not None and ans[u][ss] <= dd:
#         continue
#     ans[u][ss] = dd
    
    if done[u][ss]:
        continue
    done[u][ss] = True
    
    # グラフの隣接点
    for v in ns[u]:
        e= uv2e[u,v]
        if ss<a[e] or done[v][ss-a[e]] :
            continue
        ans[v][ss-a[e]] = min(ans[v][ss-a[e]], dd + b[e]) if ans[v][ss-a[e]] is not None else dd+b[e]
#         if ss<a[e] or ans[v][ss-a[e]] is not None:
#             continue
        heapq.heappush(h, (dd + b[e], v, ss-a[e]))
    # 両替
    if ss+c[u] <= maxs:
        sss = ss+c[u]
    elif ss < maxs:
        sss = maxs
    heapq.heappush(h, (dd + d[u], u, sss))
    ans[u][sss] = min(ans[u][sss], dd + d[u]) if ans[u][sss] is not None else dd+d[u]

for item in ans[1:]:
    print(min(item))

### FIXED CODE ###



import heapq
from collections import defaultdict
h = []
heapq.heapify(h)

n, m, s = list(map(int, input().split()))
a, b = [[None] * m for _ in range(2)]
c, d = [[None] * n for _ in range(2)]

ns = defaultdict(list)
uv2e = {}
for i in range(m):
    u,v,a[i],b[i] = list(map(int, input().split()))
    ns[u-1].append(v-1)
    ns[v-1].append(u-1)
    uv2e[u-1,v-1] = i
    uv2e[v-1,u-1] = i
for i in range(n):
    c[i], d[i] = list(map(int, input().split()))

maxs = max(a)*(n-1)
s = min(s, maxs)
state = (0, 0, s) # (距離, ノード, 銀貨枚数)
ans = [[None] * (maxs+1) for _ in range(n)]
heapq.heappush(h, state)
count = 0
while h:
    count += 1
    dd, u, ss = heapq.heappop(h)
#     print(dd, u, ss)
    if ans[u][ss] is not None and ans[u][ss] <= dd:
        continue
    ans[u][ss] = dd
    
    # グラフの隣接点
    for v in ns[u]:
        e= uv2e[u,v]
        if ss<a[e] or ans[v][ss-a[e]] is not None:
            continue
        heapq.heappush(h, (dd + b[e], v, ss-a[e]))
    # 両替
    if ss+c[u] <= maxs:
        heapq.heappush(h, (dd + d[u], u, ss+c[u]))
    elif ss < maxs:
        heapq.heappush(h, (dd + d[u], u, maxs))

for item in ans[1:]:
    print(min(item))
K = input()
S = input()K = int(input())
S = input()
if len(S) <= K:
  print(S)
else:
  print(S[:K] + "...")

### FIXED CODE ###

K = int(input())
S = input()
if len(S) <= K:
  print(S)
else:
  print(S[:K] + "...")
n = int(input())
t = list(map(int,input().split()))
m = int(input())
PX = [list(map(int,input().split())) for _ in range(m)]
ans = 10**7
s1 = sum(t)
for i in range(m):
  s2 = s1 - t[PX[i][0]] + PX[i][1]
  ans = min(ans,s2)                         
print(ans)  

### FIXED CODE ###

n = int(input())
t = list(map(int,input().split()))
m = int(input())
PX = [list(map(int,input().split())) for _ in range(m)]
s = sum(t)
for i in range(m):
  ans = s - t[PX[i][0]-1] + PX[i][1]   
  print(ans)
a, b = map(int,input().split( ))
if a >= 13:
    b = b
elif 6 <= a <= 12:
    int(b = b / 2)
else:
   b = 0
print(b)

### FIXED CODE ###

a, b = map(int,input().split( ))
if a >= 13:
    b = b
elif 6 <= a <= 12:
    b = b / 2
else:
   b = 0
print(int(b))
def main():
  s = input()
  n = len(s)
  x, y = map(int, input().split())

  dpx = [[False, False] for _ in range(n)]
  dpy = [[False, False] for _ in range(n)]

  dpx[0][0] = True
  dpy[0][0] = True
  x_turn = False
  y_turn = False
  judge = True
  turn = False
  xcount = 0
  count = 0
  for i in range(n):
    if judge and s[i] == "F":
      xcount += 1
      continue
    if judge:
      judge = False
      turn = False if turn else True
      continue
    if s[i] == "F":
      count += 1
      if i != n-1:
        continue
    if turn:
      y_turn = False if y_turn else True
      if y_turn:
        p, q = 0, 1
      else:
        p, q = 1, 0
      for i in range(n+1):
        
        dpy[i][q] = False
      for i in range(n+1):
        if dpy[i][p]:
          dpy[abs(i-count)][q] = True
          dpy[i+count][q] = True
    else:
      x_turn = False if x_turn else True
      if x_turn:
        p, q = 0, 1
      else:
        p, q = 1, 0
      for i in range(n+1):
        dpx[i][q] = False
      for i in range(n+1):
        if dpx[i][p]:
          dpx[abs(i-count)][q] = True
          dpx[i+count][q] = True
    turn = False if turn else True
    count = 0
  
  p = 1 if x_turn else 0
  q = 1 if y_turn else 0
  x -= xcount
  if abs(x) > n:
    print("No")
  elif dpx[abs(x)][p] and dpy[abs(y)][q]:
    print("Yes")
  else:
    print("No")
  
if __name__ == "__main__":
  main()

### FIXED CODE ###

def main():
  s = input()
  n = len(s)
  x, y = map(int, input().split())

  dpx = [[False, False] for _ in range(n+2)]
  dpy = [[False, False] for _ in range(n+2)]

  dpx[0][0] = True
  dpy[0][0] = True
  x_turn = False
  y_turn = False
  judge = True
  turn = False
  xcount = 0
  count = 0
  for i in range(n):
    if judge and s[i] == "F":
      xcount += 1
      continue
    if judge:
      judge = False
      turn = False if turn else True
      continue
    if s[i] == "F":
      count += 1
      if i != n-1:
        continue
    if turn:
      y_turn = False if y_turn else True
      if y_turn:
        p, q = 0, 1
      else:
        p, q = 1, 0
      for i in range(n+1):
        
        dpy[i][q] = False
      for i in range(n+1):
        if dpy[i][p]:
          dpy[abs(i-count)][q] = True
          dpy[i+count][q] = True
    else:
      x_turn = False if x_turn else True
      if x_turn:
        p, q = 0, 1
      else:
        p, q = 1, 0
      for i in range(n+1):
        dpx[i][q] = False
      for i in range(n+1):
        if dpx[i][p]:
          dpx[abs(i-count)][q] = True
          dpx[i+count][q] = True
    turn = False if turn else True
    count = 0
  
  p = 1 if x_turn else 0
  q = 1 if y_turn else 0
  x -= xcount
  if abs(x) > n:
    print("No")
  elif dpx[abs(x)][p] and dpy[abs(y)][q]:
    print("Yes")
  else:
    print("No")
  
if __name__ == "__main__":
  main()
from math import min
s = input()
st = input()
mx=10**5

rangeforloop= len(s)+1 - len(st)
 
for i in range(rangeforloop):
    mx=min(mx,matcher(s[i:len(st)+i], st))
    
     
print(mx)

### FIXED CODE ###

def matcher(s1,s2):
    match=0
    for i in range(len(s1)):
        if(s1[i]!=s2[i]):
            match+=1
            
    return match

#print(matcher("eforces","atcoder"))

s = input()
st = input()
mx=10**5

rangeforloop= len(s)+1 - len(st)
 
for i in range(rangeforloop):
    mx=min(mx,matcher(s[i:len(st)+i], st))
    
     
print(mx)
print((3*int(input())+int(input()))//2)

### FIXED CODE ###

a, p = map(int, input().split())
print((3 * a + p) // 2)
a,b=input().split()
a=int(a)
b=(float(b)*100)
print(string(a*b)[:-2])

### FIXED CODE ###

a,b=input().split()
a=int(a)
b=b.replace(".","")
b=int(b)
ans=str(a*b)
if (len(ans)>=3):
    print(ans[:-2])
else:
    print(0)
from collections import deque
HW = input().split()
H, W = int(HW[0]), int(HW[1])
C = input().split()
Ch, Cw = int(C[0]), int(C[1])
D = input().split()
Dh, Dw = int(D[0]), int(D[1])
route = []
for h in range(H):
    route.append(input())


visited = [[False]*W for x in range(H)]
kouho = deque()
kouho.append([Ch-1, Cw-1])
warpkouho = deque()

def check_walk(a, b):
    if 0 <= a <= H-1 and 0 <= b <= W-1: 
        if visited[a][b] == False and route[a][b] == ".":
            kouho.append([a, b])
def check_warp(a, b, cwarp):
    if 0 <= a <= H-1 and 0 <= b <= W-1:
        if visited[a][b] == False and route[a][b] == ".":
            warpkouho.append([a, b, cwarp+1])

def wizard():
    warp = 1
    while True:
        if len(kouho) != 0:
            tmp = kouho.popleft()
        elif len(warpkouho) != 0:
            tmp = warpkouho.popleft()
            warp = tmp[2]
        else:
            break
        h = tmp[0]
        w = tmp[1]
        if visited[h][w] == False:
            visited[h][w] = warp
            check_walk(h-1, w)
            check_walk(h+1, w)
            check_walk(h, w-1)
            check_walk(h, w+1)
            for n in range(5):
                for m in range(5):
                  	if not((n==2 and m==(1 or 2 or 3))or(n==1 and m == 2)or(n == 3 and m ==2)):                    	
                    check_warp(h-2+n, w-2+m, warp)
    if h == Dh-1 and w == Dw-1:
      	print(visited[h][w]-1)
      	return
    print(-1)
wizard()

        

### FIXED CODE ###

from collections import deque
HW = input().split()
H, W = int(HW[0]), int(HW[1])
C = input().split()
Ch, Cw = int(C[0]), int(C[1])
D = input().split()
Dh, Dw = int(D[0]), int(D[1])
route = []
for h in range(H):
    route.append(input())

visited = [[False]*W for x in range(H)]
kouho = deque()
kouho.append([Ch-1, Cw-1])
warpkouho = deque()

def check_walk(a, b):
    if 0 <= a <= H-1 and 0 <= b <= W-1: 
        if visited[a][b] == False and route[a][b] == ".":
            kouho.append([a, b])
def check_warp(a, b, cwarp):
    if 0 <= a <= H-1 and 0 <= b <= W-1:
        if visited[a][b] == False and route[a][b] == ".":
            warpkouho.append([a, b, cwarp+1])

def wizard():
    warp = 1
    while True:
        if len(kouho) != 0:
            tmp = kouho.popleft()
        elif len(warpkouho) != 0:
            tmp = warpkouho.popleft()
            warp = tmp[2]
        else:
            break
        h = tmp[0]
        w = tmp[1]
        if visited[h][w] == False:
            visited[h][w] = warp
            check_walk(h-1, w)
            check_walk(h+1, w)
            check_walk(h, w-1)
            check_walk(h, w+1)
            for n in range(5):
                for m in range(5):
                  check_warp(h-2+n, w-2+m, warp)
        if h == Dh-1 and w == Dw-1:
            print(visited[h][w]-1)
            return
    print(-1)
wizard()
N = int(input())
l=[int(input()) for i in range(N)]
l.sort()
res = 0
k = 0
o = 0
if N%2 == 0:
    a = l[:int(N/2)]
    a.reverse()
    b = l[int(N/2):]
    b.reverse()
    for i in range(N-1):
        res += b[k] - a[o]
        if i%2 == 0:
            o += 1
        if i%2 == 1:
            k += 1
else:
    a = l[:int(N/2)]
    b = l[int(N/2)+1:]
    b.reverse()
    for i in range(N-2):
        res += b[k] - a[o]
        if i%2 == 0:
            k += 1
        if i%2 == 1:
            o += 1
    res += max(abs(a[-1] - l[int(N/2)]), abs(b[-1] - l[int(N/2)]))
print(res)


### FIXED CODE ###

N = input()
a = N.split()
if len(N) == 2:
    print(N)
else:
    print(N[2]+N[1]+N[0])
from collections import Counter as c

e,o = 0,0
ans = 0
E,O = [],[]
for v,i in zip(V,range(N)):
    if i%2 == 0:
        E.append(v)
    else:
        O.append(v)
EC = c(E).most_common()
OC = c(O).most_common()
n = N//2

EC01=EC[0][1]

OC01=OC[0][1]

if len(EC) == 1:
    EC11 = 0
else:
    EC11=EC[1][1]
if len(OC) == 1:
    OC11 = 0
else:
    OC11=OC[1][1]
if len(EC) == 1 and len(OC) == 1 and EC[0][0]==OC[0][0]:
    ans = EC01
elif EC01+OC11 > EC11+OC01:
    ans += n - EC01
    ans += n - OC11
elif EC01+OC11 < EC11+OC01:
    ans += n - EC11
    ans += n - OC01
elif EC01 == OC01:
    ans = 0
print(EC01,EC11,OC01,OC11)
print(ans)

### FIXED CODE ###

from collections import Counter as c

N = int(input())
V = list(map(int,input().split()))
ev = c(V[::2]).most_common(2)
od = c(V[1::2]).most_common(2)

if ev[0][0] == od[0][0]:
    if len(ev) == 1 and len(od) == 1:
        print(N//2)
    else:
        print(N-max(ev[0][1]+od[1][1],ev[1][1]+od[0][1]))
else:
    print(N-ev[0][1]-od[0][1])
ans = 0
for i in range(n+1):
  s = str(input())
  if s.count('7')+s.count('5')+s.count('3') == int(s):
    ans += 1
print(ans)


### FIXED CODE ###

N = int(input())

ans = 0
a = [3, 5, 7]
i = 0
while a[i] <= N:
    x10 = a[i] * 10
    a.append(x10+3)
    a.append(x10+5)
    a.append(x10+7)
    i += 1

for j in range(i):
    s = str(a[j])
    if "3" in s and "5" in s and "7" in s:
        ans += 1

print(ans)
volume = x * x * x
print int(volume)

### FIXED CODE ###

x = input()
cube = x * x * x
print cube
S = []
for _ in range(2):
    S.append(input())

if S == [1, 2]
  print('3')
elif S == [2, 1]:
  print('3')
elif S == [1, 3]:
  print('2')
elif S == [3, 1]:
  print('2')
elif S == [2, 3]:
  print('1')
elif S == [3, 2]:
  print('1')

### FIXED CODE ###

a = int(input())
b = int(input())
c = a + b

if c == 3:
  print('3')
elif c == 4:
  print('2')
else:
  print('1')
S=input()
S+="1"
A=[]
count1=0
count2=0
total=0
for i in range(60):
    total+=i
    A.append(total)

total=0
for i in range(len(S)):
    if S[i]=="<":
        count1+=1
    if S[i]==">":
        count2+=1
    if S[i]==">" and S[i+1]=="<":
        total+=A[max(count1,count2)]
        if min(count1, count2) != 0:
            total+=A[min(count1,count2)-1]
        #print(count1, count2,total)
        count1=0
        count2=0

total+=A[max(count1,count2)]
if min(count1,count2)!=0:
    total+=A[min(count1,count2)-1]
#print(A)
#print(count1,count2)


print(total)


### FIXED CODE ###

S=input()
S+="1"
A=[]
count1=0
count2=0
total=0
for i in range(600000):
    total+=i
    A.append(total)

total=0
for i in range(len(S)):
    if S[i]=="<":
        count1+=1
    if S[i]==">":
        count2+=1
    if S[i]==">" and S[i+1]=="<":
        total+=A[max(count1,count2)]
        if min(count1, count2) != 0:
            total+=A[min(count1,count2)-1]
        #print(count1, count2,total)
        count1=0
        count2=0

total+=A[max(count1,count2)]
if min(count1,count2)!=0:
    total+=A[min(count1,count2)-1]
#print(A)
#print(count1,count2)


print(total)
A, B, C = map(int, input().split())

coin_sound_cnt = B//A
if coin_sound_cnt > C:
  return C
else:
  return coin_sound_cnt


### FIXED CODE ###

A, B, C = map(int, input().split())

coin_sound_cnt = B//A
if coin_sound_cnt > C:
  print(C)
else:
  print(coin_sound_cnt)
import math

A, B = map(int, input().split())
ans = A * B // math.gcd(A,B)

print(ans)

### FIXED CODE ###

from fractions import gcd

A,B = map(int,input().split())
answer = A * B // gcd(A,B)
print(answer)
S = list(input())
T = list(input())
l = 0
for i in range(len(s)):
  if S[i] == T[i]:
    l += 1
print(l)

### FIXED CODE ###

S = list(input())
T = list(input())
l = 0
for i in range(len(S)):
  if S[i] == T[i]:
    l += 1
print(l)
from collections import defaultdict
from bisect import bisect_right

""" Binary Indexed Tree """
class BIT:

    def __init__(self, N):
        self.N = N
        self.bit = [0] * (N+1)

    def add(self, x, a):
        while x <= self.N:
            self.bit[x] += a
            x += x & -x

    def sum(self, x):
        ret = 0
        while x != 0:
            ret += self.bit[x]
            x -= x & -x
        return ret

    # x < sum(index) となる最小の index を返す
    def upper_bound(self, x):
        l, r = -1, self.N
        while l+1 < r:
            m = (l+r)//2
            y = self.sum(m)
            if x < y:
                r = m
            else:
                l = m
        return r

    # x <= sum(index) となる最小の index を返す
    def lower_bound(self, x):
        l, r = -1, self.N
        while l+1 < r:
            m = (l+r)//2
            y = self.sum(m)
            if y < x:
                l = m
            else:
                r = m
        return r

N, Q = map(int, input().split())
c = list(map(int, input().split()))
rl = [None] * Q
for i in range(Q):
    l, r = map(int, input().split())
    rl[i] = (r, l, i)
rl.sort()
bit = BIT(N+1)
ans = [None] * Q
last_idx = [-1] * N
j = 0
for r, l, i in rl:
    while j < r:
        if last_idx[c[j]] == -1:
            last_idx[c[j]] = j
        else:
            bit.add(last_idx[c[j]]+1, -1)
            last_idx[c[j]] = j
        bit.add(j+1, 1)
        j += 1
    ans[i] = bit.sum(r) - bit.sum(l-1)
print(*ans, sep='\n')
            

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    N, Q = map(int, input().split())
    bit = [0] * (N+1)

    def add(x, a):
        while x <= N:
            bit[x] += a
            x += x & -x

    def sum(x):
        ret = 0
        while x != 0:
            ret += bit[x]
            x -= x & -x
        return ret

    c = list(map(int, input().split()))
    lr = [None] * Q
    for i in range(Q):
        l, r = map(int, input().split())
        lr[i] = (i, l, r)
    lr.sort(key=lambda x: x[2])
    ans = [None] * Q
    last_idx = [-1] * (N+1)
    j = 0
    for i, l, r in lr:
        while j < r:
            if last_idx[c[j]] == -1:
                last_idx[c[j]] = j
            else:
                add(last_idx[c[j]]+1, -1)
                last_idx[c[j]] = j
            add(j+1, 1)
            j += 1
        ans[i] = sum(r) - sum(l-1)
    for a in ans:
        print(a)
            
if __name__ == "__main__":
    main()
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7

def LI(): return list(map(int,input().split()))
def I(): return int(input())
def LS(): return input().split()
def S(): return input()

def main():
  n,k=LI()
  l=LI()

  dp=[inf]*11
  dp[0]=0

  for j in range(n):
    for i in range(1,k+1):
      if i+j<n:
        dp[i+j]=min(dp[i+j],dp[j]+abs(l[i+j]-l[j]))

  return dp[n-1]

print(main())


### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7

def LI(): return list(map(int,input().split()))
def I(): return int(input())
def LS(): return input().split()
def S(): return input()

def main():
  n,k=LI()
  l=LI()

  dp=[inf]*100010
  dp[0]=0
  for i in range(n):
    for j in range(1,k+1):
      if i+j<n:
        dp[i+j]=min(dp[i+j],dp[i]+abs(l[i+j]-l[i]))

  return dp[n-1]

print(main())
import numpy as np

N,M = map(int, input().split())
t_table = {}
for i in range(M):
	x,y = map(int, input().split())
	if x-1 in t_table: t_table[x-1].append(y-1)
	else: t_table[x-1] = [y-1]
mem = np.zeros(N, dtype='int32')
ans = 0
ccheck = [True for _ in range(N)]
NodeList = np.array([i for i in range(N)])
while True:
	p_mem = mem.copy()
	p_cnt = np.zeros(N, dtype='int32')
	for i in NodeList[ccheck]:
		if i in t_table :
			p_cnt[t_table[i]] = 1
	mem+=p_cnt
	ccheck = (mem!=p_mem)
	if((mem==p_mem).all()):
	 	print(ans)
	 	break
	ans += 1

### FIXED CODE ###

import sys

sys.setrecursionlimit(10**5+10)
input = sys.stdin.readline

N,M = map(int, input().split())
lst_edge = [[] for _ in range(N)]
for _ in range(M):
	x,y = map(int, input().split())
	lst_edge[x-1].append(y-1)

dp = [-1] * N

def rec(v):
	if dp[v] != -1:
		return dp[v]
	ans = 0
	lst_nv = lst_edge[v]
	for nv in lst_nv:
		ans = max(ans, rec(nv)+1)
	dp[v] = ans
	return dp[v]

ans = 0
for v in range(N):
	ans = max(ans,rec(v))
print(ans)
import math

X, K, D = map(int, input().split())

a = X - K * D
if a > 0:
    print(a)
    return
if a + 2 * K * D < 0:
    print(abs(a + 2 * K * D))
    return
else:
    b = a / (-2 * D)
    p = math.floor(b)
    q = math.ceil(b)
    r = -(a + 2 * D * p)
    s = a + 2 * D * q
    print(min(r,s))
    return


### FIXED CODE ###

import math
import sys

X, K, D = map(int, input().split())

a = X - K * D
if a > 0:
    print(a)
    sys.exit()
if a + 2 * K * D < 0:
    print(abs(a + 2 * K * D))
    sys.exit()
else:
    b = a / (-2 * D)
    p = math.floor(b)
    q = math.ceil(b)
    r = -(a + 2 * D * p)
    s = a + 2 * D * q
    print(min(r,s))
    sys.exit()