Harryxun/stf_run huggingface dataset:
N,K = map(int, input().split())
S = input()


if S[K] == "A":
    S[K] = "a"
elif S[K] == "B":
    S[K] = "b"
elif S[K] == "C":
    S[K] = "c"

print(S)

### FIXED CODE ###

n, k = map(int,input().split())
s = list(input())
 
if s[k-1] == "A":
  s[k-1] = "a"
elif s[k-1] == "B":
  s[k-1] = "b"
elif s[k-1] == "C":
  s[k-1] = "c"
 
print("".join(s))
a,b,c=[int(x) in x for input().split()]
if a<b<c:
    print(a,b,c,sep=" ")
elif a<c<b:
    print(a,c,b,sep=" ")
elif b<a<c:
    print(b,a,c,sep=" ")
elif b<c<a:
    print(b,c,a,sep=" ")
elif c<a<b:
    print(c,a,b,sep=" ")
elif c<b<a:
    print(c,b,a,sep=" ")



### FIXED CODE ###

a,b,c=[int(x) for x in input().split()]
if a<=b<=c:
    print(a,b,c)
elif a<=c<=b:
    print(a,c,b)
elif b<=a<=c:
    print(b,a,c)
elif b<=c<=a:
    print(b,c,a)
elif c<=a<=b:
    print(c,a,b)
elif c<=b<=a:
    print(c,b,a)
S = list(input())
ans = 0
if len(S)>=2:
    for i in range(0, len(S), 2):
        if S[i]!="h" or S[i+1]!="i":
            ans += 1
    if ans==0:
        print("Yes")
    else:
        print("No")
else:
    print("No")

### FIXED CODE ###

S = input()
list = ["hi","hihi","hihihi","hihihihi","hihihihihi"]
if S in list:
    print("Yes")
else:
    print("No")
INF = float("inf")

H,W = map(int,input().split())
ans = INF
for i in range(1,H):
    SA = i * W
    #横半分に分割するケース
    h = math.ceil((H-i)/2)
    SB1 = h * W
    SC1 = (H-i-h)*W
    S1 = max(SA,SB1,SC1)-min(SA,SB1,SC1)
    #縦半分に分割するケース
    w = math.ceil(W/2)
    SB2 = (H-i)*w
    SC2 = (H-i)*(W-w)
    S2 = max(SA,SB2,SC2)-min(SA,SB2,SC2)
    ans = min(ans,S1,S2)
print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-
import itertools
import math
from collections import deque
from collections import defaultdict
from itertools import permutations
import heapq
import bisect
from scipy.sparse.csgraph import floyd_warshall as wf
INF = float("inf")

H,W = map(int,input().split())
ans = INF

for i in range(1,H):
    SA = i * W
    h = (H-i)//2
    w = W//2
    SB2 = (H-i)*w
    SC2 = H*W-(SA+SB2)
    SB1 = h * W
    SC1 = H*W-(SA+SB1)
    S1 = max(SA,SB1,SC1)-min(SA,SB1,SC1)
    S2 = max(SA,SB2,SC2)-min(SA,SB2,SC2)
    ans = min(ans,S1,S2)

for i in range(1,W):
    SA = H * i
    #横半分に分割するケース
    h = H//2
    w = (W-i)//2
    SB1 = h * (W-i)
    SC1 = H*W-(SA+SB1)
    S1 = max(SA,SB1,SC1)-min(SA,SB1,SC1)
    #縦半分に分割するケース
    SB2 = H*w
    SC2 = H*W -(SA+SB2)
    S2 = max(SA,SB2,SC2)-min(SA,SB2,SC2)
    ans = min(ans,S1,S2)

print(ans)
S = input()
T = input()

for i in range(len(S)):
	s = S[len(S)]
	S'= S[0:-1]
	if S==T
		print("Yes")
		break
	S = s + S'
else:
	print("No")
		

### FIXED CODE ###

S = input()
T = input()

for i in range(len(S)):
	if T==S:
		print("Yes")
		break
	S = S[-1]+ S[0:-1]
else:
	print("No")
n = input()
return (n // 2) + (n % 2) 

### FIXED CODE ###

n = int(input())
ans = (n // 2) + (n % 2)
print(ans)
import bisect
N, P = map(int, input().split())
if N == 1:
    print(P)
    exit()

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


div_list = make_divisors(P)
ans = 0
for i in range(10 ** 6 + 1):
    idx = bisect.bisect_left(div_list, i ** N)
    if i ** N == div_list[min(idx, len(div_list) - 1)]:
        ans = i
print(ans)

### FIXED CODE ###

def solve(N, P):
    prime_list = []
    for i in range(2, int(P ** (1 / 2)) + 1):
        cnt = 0
        while P % i == 0:
            cnt += 1
            P //= i
        if cnt:
            prime_list.append([i, cnt])
    if P != 1:
        prime_list.append([P, 1])

    ans = 1
    for prime, cnt in prime_list:
        if cnt >= N:
            ans *= prime ** (cnt // N)
    return ans

if __name__ == '__main__':
    n, p = map(int, input().split())
    print(solve(n, p))
K,X=map(int,input().split)
if 500*K<X:
  print("No")
else:
  print("Yes")

### FIXED CODE ###

K,X=map(int,input().split())
if 500*K>=X:
  print("Yes")
else:
  print("No")
s=input()
k=int(input())
l=[]
for i in range(n):
  for j in range(i:n):
    a=s[i:j+1]
    l.append(a)
l=set(l)
l.sort()
print(l[k-1])

### FIXED CODE ###

s=input()
n=len(s)
k=int(input())
l=[]
for i in range(n):
  for j in range(i,i+k+1):
    a=s[i:j+1]
    l.append(a)
l=set(l)
l=list(l)
l.sort()
print(l[k-1])
N = int(input())
A = list(map(int, input().split()))

def up(i,pre):
    if i == len(A) - 1:
        return abs(A[pre] - A[i])
    res1 = res2 = float("inf")
    res1 = up(i + 1,i)
    if i + 2 <=len(A) -1: 
        res2 = up(i + 2,i)
    return min(abs(A[pre] - A[i]) + res1,abs(A[pre] - A[i]) + res2)

if N > 2:
    print(min(up(1,0),up(2,0)))
else:
    print(up(1,0))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
dp = [0 for _ in range(len(A))]
dp[0] = 0 
for i in range(1,N):
    if i - 2>=0:
        dp[i] = min(dp[i-1] + abs(A[i] - A[i-1]),dp[i-2] + abs(A[i] - A[i-2]))
    else:
        dp[i] =dp[i-1] + abs(A[i] - A[i-1])

print(dp[len(A)-1])
a=$1-$2,ans=$3-a{print ans}

### FIXED CODE ###

A,B,C = input().split()
ans = int(C)-int(A)+int(B)
if(ans>=0):
  print(ans)
else:
  print("0")
N, D = map(int, input().split())
Ps = []
count = 0

for i in range(N):
  P = list(map(int, input().split()))
  Ps.append(P)

def dis2(A, B):
  dis = 0
  for i in range(D):
    dis += (A[i] - B[i])**2
  return dis

for i in range(N-1):
  for j in range(i+1, N):
    if math.sqrt(dis2(Ps[i], Ps[j])).is_integer():
      count += 1

print(count)

### FIXED CODE ###

import math

N, D = map(int, input().split())
Ps = []
count = 0

for i in range(N):
  P = list(map(int, input().split()))
  Ps.append(P)

def dis2(A, B):
  dis = 0
  for i in range(D):
    dis += (A[i] - B[i])**2
  return dis

for i in range(N-1):
  for j in range(i+1, N):
    if math.sqrt(dis2(Ps[i], Ps[j])).is_integer():
      count += 1

print(count)
from collections import deque
import sys
sys.setrecursionlimit(20000000)

N = int(input())
ab = [list(map(int, input().split())) for _ in range(N-1)]
routes = [[] for _ in range(N)]

for i in range(len(ab)):
    routes[ab[i][0]-1].append([ab[i][1]-1, i])
    routes[ab[i][1]-1].append([ab[i][0]-1, i])

route_color = [-10e+10 for _ in range(len(ab))]

route_num = [0]*N
max_route = 0
for i in range(N):
    num = len(routes[i])
    route_num[i] = num
    if max_route < num:
        max_route = num

seen = [False for _ in range(N)]

def function(num):
    colors = set(range(max_route))
    for route in routes[num]:
        if route_color[route[1]] != -10e+10:
            colors.remove(route_color[route[1]])
        else:
            route_color[route[1]] = colors.pop()
        if seen[route[0]] == False:
            seen[route[0]] = True
            function(route[0])
    return

function(0)
print(max_route)
for color in route_color:
    print(color+1)

### FIXED CODE ###

from collections import deque
import sys
sys.setrecursionlimit(20000000)

N = int(input())
ab = [list(map(int, input().split())) for _ in range(N-1)]
routes = [[] for _ in range(N)]

for i in range(len(ab)):
    routes[ab[i][0]-1].append([ab[i][1]-1, i])
    routes[ab[i][1]-1].append([ab[i][0]-1, i])

route_color = [-10e+10 for _ in range(len(ab))]

route_num = [0]*N
max_route = 0
for i in range(N):
    num = len(routes[i])
    route_num[i] = num
    if max_route < num:
        max_route = num

seen = [False for _ in range(N)]

def function(num,pre_color):
    color_num = -1
    for route in routes[num]:
        color_num += 1
        if color_num == pre_color:
            color_num+=1
        if route_color[route[1]] != -10e+10:
            color_num-=1
            pass
        else:
            route_color[route[1]] = color_num
            
        if seen[route[0]] == False:
            seen[route[0]] = True
            function(route[0],route_color[route[1]])
    return

function(0,-1)
print(max_route)
for color in route_color:
    print(color+1)
from _collections import deque
from _ast import Num


def parser():
    while 1:
        data = list(input().split(' '))
        for number in data:
            if len(number) > 0:
                yield (number)


input_parser = parser()


def gw():
    global input_parser
    return next(input_parser)


def gi():
    data = gw()
    return int(data)


MOD = int(1e9 + 7)

import numpy
from collections import deque
from math import sqrt
from math import floor
import heapq
# https://atcoder.jp/contests/agc033/tasks/agc033_b
# B - LRUD Game
"""
"""
N = gi()
M = gi()
g = [[] for i in range(N + 1)]

for i in range(M):
    x = gi()
    y = gi()
    z = gi()
    g[x].append(y)
    g[y].append(x)

visited = [0] * (N + 1)


def dfs(v):
    if visited[v]:
        return
    visited[v] = 1

    for u in g[v]:
        dfs(u)


ans = 0
for v in range(1, N + 1):
    if visited[v]:
        continue
    ans += 1
    dfs(v)

print(ans)


### FIXED CODE ###

from _collections import deque
from _ast import Num


def parser():
    while 1:
        data = list(input().split(' '))
        for number in data:
            if len(number) > 0:
                yield (number)


input_parser = parser()


def gw():
    global input_parser
    return next(input_parser)


def gi():
    data = gw()
    return int(data)


MOD = int(1e9 + 7)

import numpy
from collections import deque
from math import sqrt
from math import floor
import heapq
# https://atcoder.jp/contests/agc033/tasks/agc033_b
# B - LRUD Game
"""
"""
N = gi()
M = gi()
parent = [[] for i in range(N + 1)]


def find(a):
    if parent[a] != a:
        parent[a] = find(parent[a])

    return parent[a]


def union(a, b):
    aP = find(a)
    bP = find(b)

    if (aP != bP):
        parent[max(aP, bP)] = min(aP, bP)


for i in range(N + 1):
    parent[i] = i

for i in range(M):
    x = gi()
    y = gi()
    z = gi()
    union(x, y)

ans = 0

for i in range(1, N + 1):
    if find(i) == i:
        ans += 1

print(ans)
# -*- coding: utf-8 -*-
"""
Created on Thu Feb 28 16:53:54 2019

@author: またの
"""

N,M=map(int,input().split())
L = []
for i in range(N):
    L.append(list(map(int,input().split())))

K1=[]
K2=[]
K3=[]
K4=[]
K5=[]
K6=[]
K7=[]
K8=[]

C = [0,0,0,0,0,0,0,0]

for i in range(N):
    K1.append(L[i][0]+L[i][1]+L[i][2])
K1.sort()

for i in range(N):
    K2.append(L[i][0]-L[i][1]+L[i][2])
K2.sort()

for i in range(N):
    K3.append(L[i][0]+L[i][1]-L[i][2])
K3.sort()

for i in range(N):
    K4.append(-L[i][0]+L[i][1]+L[i][2])
K4.sort()

for i in range(N):
    K5.append(-L[i][0]+L[i][1]-L[i][2])
K5.sort()

for i in range(N):
    K6.append(L[i][0]-L[i][1]-L[i][2])
K6.sort()

for i in range(N):
    K7.append(-L[i][0]-L[i][1]+L[i][2])
K7.sort()

for i in range(N):
    K8.append(-L[i][0]-L[i][1]-L[i][2])
K8.sort()

for i in range(M):
    C[0] += K1[M-i]
    C[1] += K2[M-i]
    C[2] += K3[M-i]
    C[3] += K4[M-i]
    C[4] += K5[M-i]
    C[5] += K6[M-i]
    C[6] += K7[M-i]
    C[7] += K8[M-i]
    
for i in range(8):
    C[i] = abs(C[i])
print(max(C))


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Thu Feb 28 16:53:54 2019

@author: またの
"""

N,M=map(int,input().split())
L = []
for i in range(N):
    L.append(list(map(int,input().split())))

K1=[]
K2=[]
K3=[]
K4=[]
K5=[]
K6=[]
K7=[]
K8=[]

C = [0,0,0,0,0,0,0,0]

for i in range(N):
    K1.append(L[i][0]+L[i][1]+L[i][2])
K1.sort()

for i in range(N):
    K2.append(L[i][0]-L[i][1]+L[i][2])
K2.sort()

for i in range(N):
    K3.append(L[i][0]+L[i][1]-L[i][2])
K3.sort()

for i in range(N):
    K4.append(-L[i][0]+L[i][1]+L[i][2])
K4.sort()

for i in range(N):
    K5.append(-L[i][0]+L[i][1]-L[i][2])
K5.sort()

for i in range(N):
    K6.append(L[i][0]-L[i][1]-L[i][2])
K6.sort()

for i in range(N):
    K7.append(-L[i][0]-L[i][1]+L[i][2])
K7.sort()

for i in range(N):
    K8.append(-L[i][0]-L[i][1]-L[i][2])
K8.sort()

for i in range(M):
    C[0] += K1[N-i-1]
    C[1] += K2[N-i-1]
    C[2] += K3[N-i-1]
    C[3] += K4[N-i-1]
    C[4] += K5[N-i-1]
    C[5] += K6[N-i-1]
    C[6] += K7[N-i-1]
    C[7] += K8[N-i-1]
    
for i in range(8):
    C[i] = abs(C[i])
print(max(C))
n,k=map(int,input().split())
a=list(map(int,input().split()))

for i in range(k):
  b=[0]*n
  cnt=0
  for j in range(n):
    if a[j]>=max(n-j,j)
    cnt+=1
  if cnt==n:
    for j in range(n):
      a[j]=(k-i)*n
    break
  for j in range(n):
    for m in range(j-a[j],j+a[j]+1):
      if 0<=m<=n-1:
        b[m]=b[m]+1
  a=b
for i in a:
  print(i,end=' ')


### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
for _ in range(min(k,41)):
  b=[0]*(n+1)
  for i in range(n):
    l=max(0,i-a[i])
    r=min(n,i+a[i]+1)
    b[l]+=1
    b[r]-=1
  for i in range(n-1):
    b[i+1]+=b[i]
  a=b[:n]
print(*a)
# -*- coding: utf-8 -*-
a = int(input())  # Nを入力
b = input()  # a1,a2...anを入力
b = map(int, b.split())  # a1,a2...anをint型でリストに入れる
b = sorted(b)  # 大きい順に並べる b = b[::-1]  # リストの要素の順番を逆転する
c = b[::2]  # Aliceのとる要素を抽出
c_number = len(c)
d = b[1::2]  # Bobのとる要素を抽出
d_number = len(d)
c_sum = 0
d_sum = 0
for i in range(c_number):
    c_sum += c[i] # Aliceのとる要素の合計
for g in range(d_number):
    d_sum += d[g]  # Bobのとる要素の合計
print(c_sum - d_sum)  # 差分を出力


### FIXED CODE ###

# -*- coding: utf-8 -*-
a = int(input())  # Nを入力
b = input()  # a1,a2...anを入
b = map(int, b.split())
b = sorted(b)
b = b[::-1]
c = b[::2]
c_number = len(c)
d = b[1::2]
d_number = len(d)
c_sum = 0
d_sum = 0
for i in range(c_number):
    c_sum += c[i]

for g in range(d_number):
    d_sum += d[g]

print(c_sum - d_sum)
import fractions

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

a_re = []
b_re = []

for i in range(max(A,B)//2 +1):
    if i == 0:
        continue
    if A % i ==0:
        a_re.append(i)
    if B % i ==0:
        b_re.append(i)

result = list (set(a_re) & set( b_re))
result.sort(reverse=True)

print(result)
print(result[K-1])

### FIXED CODE ###

import fractions

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

a_re = []
b_re = []

for i in range(max(A,B) + 1):
    if i == 0:
        continue
    #print(i)
    if A % i ==0:
        a_re.append(i)
    if B % i ==0:
        b_re.append(i)
#print(a_re)

result = list (set(a_re) & set( b_re))

result.sort(reverse=True)
print(result[K-1])
import math
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

a, b, c, d = map(int, read().split())

g = int(c * d / math.gcd(c, d))

b_c = b // c
b_d = b // d
b_g = b // g
a_c = (a-1) // c
a_d = (a-1) // d
a_g = (a-1) // g

ans = (b - b_c - b_d + b_g) - ((a-1) - a_c - a_d + a_g)
print(ans)


### FIXED CODE ###

from fractions import gcd

a, b, c, d = map(int, input().split())
g = int(c * d / gcd(c, d))
print((b - b // c - b // d + b // g) - ((a-1) - (a-1) // c - (a-1) // d + (a-1) // g))
import numpy as np
N,K = map(int, input().split())
p = np.array(list(map(int,input().split())))
p = (p+1)/2
sorted_p = np.sort(p)[::-1]
ans = sum(sorted_p[0:K])
print(ans)


### FIXED CODE ###

import numpy as np
N,K = map(int, input().split())
p = [(int(i)+1)/2 for i in input().split()]
s = [0]*N
s[0] = p[0]
if N==K:
    print(sum(p))
else:
    for i in range(N-1):
        s[i+1] = s[i]+p[i+1]
    ans=max(s[i+K]-s[i] for i in range(N-K))
    print(ans)
N, K = map(int, input().split())
x = [int(i) for i in input().split()]
a = []
a2 = []
for i in x:
    if i < 0:
        a2.append(2 * abs(i))
    else:
        a.append(i)

if len(a2) == 0:
    print(a[K-1])
    exit()
a2 = sorted(a2)
c1 = float('inf')

for i, v in enumerate(a):
    if K - i > len(a2):
        continue
    c1 = min(c1, v + a2[K - i])

b = []
b2 = []
for i in x:
    if i > 0:
        b2.append(2 * abs(i))
    else:
        b.append(-i)
b = sorted(b)

if len(b2) == 0:
    print(b[K-1])
    exit()

c2 = float('inf')
for i, v in enumerate(b):
    if K - i > len(b2):
        continue
    c2 = min(c2, v + b2[K - i])

print(min(c1,c2))

### FIXED CODE ###

N, K = map(int, input().split())
x = [int(i) for i in input().split()]
ans = float('inf')
for i in range(N-K+1):
    l = x[i]
    r = x[i+K-1]
    a = abs(l) + abs(r - l)
    b = abs(r) + abs(r - l)
    ans = min(a,b,ans)
print(ans)
a=raw_input()
print(a.count("+")-a.count("-"))

### FIXED CODE ###

print(4-input().count("-")*2)
n = int(input())
a = list(int, input().split())

print(sum(a)-n)

### FIXED CODE ###

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

print(sum(a)-n)
a, b = map(int, input().split())
bits = []
for i in range(b.bit_length()):
    k = pow(2, i+1)
    nb, rb = divmod(b, k)
    na, ra = divmod(max(0,a-1), k)

    bb = nb*(k//2) + max(0, rb - k//2 + 1)
    aa = na*(k//2) + max(0, ra - k//2 + 1)
    bits.append((bb-aa)%2)
print(int(''.join(map(str, bits[::-1])), 2))


### FIXED CODE ###

a, b = map(int, input().split())
if a == b:
    print(a)
else:
    bits = []
    for i in range(b.bit_length()):
        k = pow(2, i+1)
        nb, rb = divmod(b, k)
        na, ra = divmod(max(0,a-1), k)

        bb = nb*(k//2) + max(0, rb - k//2 + 1)
        aa = na*(k//2) + max(0, ra - k//2 + 1)
        bits.append((bb-aa)%2)
    # print(bits)
    print(int(''.join(map(str, bits[::-1])), 2))
n = int(input())

if n%2 == 0:
    print(1/2)

elif n==1:
    print(1)

else:
    print((math.ceil(n//2)+1)/n)

### FIXED CODE ###

import math
n = int(input())

if n%2 == 0:
    print(1/2)

elif n==1:
    print(1)

else:
    print((math.ceil(n//2)+1)/n)
n=int(input())
A,B = input().split()
i=0
i=int(i)
list01=[]
for d in range(n): 
  lisa=A[i]+B[i]
  list01.append(lisa)
  i+=1
for s in list01:
print(s)

### FIXED CODE ###

S=int(input())
W=int(input())
if S+W==3:
  print(3)
elif S+W==4:
  print(2)
elif S+W==5:
  print(1)
#16D8101014F 久留米 竜之介 Python

n,time=map(int,input().split())
timenow = 0
p=[]
q=[]
queue=[] #p1,p2....
Queue=[] #time
for i in range (n):
	line=input().split()
	q.append(int(line.pop()))
	p.append(line.pop())

head=0
tail=len(p)-1
while head is not tail:
	#print(p)
	#print(q)
	#print(head,tail)
	Ptmp=q[head]
	if Ptmp<=time:
		timenow+=Ptmp
		queue.append(p[head])
		Queue.append(timenow)
		head+=1
	else:
		timenow+=time
		Ptmp-=time
		q.append(Ptmp)
		p.append(p[head])
		head+=1
		tail+=1
Ptmp=q[head]
timenow+=Ptmp
queue.append(p[head])
Queue.append(timenow)

for i in range(n):
		print(queue[i],Queue[i])
		


### FIXED CODE ###

#16D8101014F 久留米 竜之介 Kurume Ryunosuke Python
All = 0
q = []
Queue = []
tmp,time = map(int,input().split())
for i in range(tmp):
    p,zi =input().split()
    q.append([p,int(zi)])
while len(q) > 0:
    if q[0][1]<= time:
        All+=q[0][1]
        v=q.pop(0)
        Queue.append([v[0],All])
    else:
        All+=time
        q[0][1]-=time
        last=q.pop(0)
        q.append(last)
for i in range(len(Queue)):
    print("{0} {1}".format(Queue[i][0],Queue[i][1]))
import numpy as np

n,m = map(int, input().split())
p = list(map(int, input().split()))
par = np.arange(n)
rank = np.zeros(n)

def root(x):
	if par[x] == x:
		return x
	else:
		return root(par[x])
def merge(x, y):
	x = root(x)
	y = root(y)
	if x == y:
		pass
	else:
		if rank[x] > rank[y]:
			par[y] = x
			rank[y] += 1
		else:
			par[x] = y
			rank[x] += 1
	pass

for i in range(m):
	x, y = map(int, input().split())
	merge(x-1, y-1)

ans = 0

for i in range(n):
	if root(p[i]-1) == root(i):
		ans += 1

print(ans)

### FIXED CODE ###

n,m = map(int, input().split())
p = list(map(int, input().split()))
par = [i for i in range(n)]
rank = [0 for x in range(n)]

def root(x):
	tmp = par[x]
	if tmp == x:
		return x
	else:
		a = root(tmp)
		par[x] = a
		return a

def merge(x, y):
	x = root(x)
	y = root(y)
	if x == y:
		return
	else:
		if rank[x] > rank[y]:
			par[y] = x
			rank[y] += rank[x]
		else:
			par[x] = y
			rank[x] += rank[y]
		return

for i in range(m):
	x, y = map(int, input().split())
	merge(x-1, y-1)

ans = 0

for i in range(n):
	if p[i]-1 == i:
		ans += 1
	elif root(p[i]-1) == root(i):
		ans += 1

print(ans)
n = int(input())
s = []
for i in range(n):
  tmp = str(input())
  tmp = "".join(sorted(tmp))
  s.append(tmp)

a = [0, 0]
for i in range(2, 10**3):
  x = a[i-1] + (i-1)
  a.append(x)

# print("s:", s)
ans = 0
for _ in list(set(s)):
  ans+= a[s.count(_)]
  
print(ans)

### FIXED CODE ###

alphabet = "abcdefghijklmnopqrstuvwxyz"


n = int(input())
res = dict()
for _ in range(n):
    s = str(input())
    freqency = [0 for _ in alphabet]
    for __ in s:
        freqency[alphabet.index(__)] += 1
    freq = "".join([str(___) for ___ in freqency])
    if freq not in res:
        res[freq] = 1
    else:
        res[freq] += 1

ans = 0
for value in res.values():
    ans += ((value-1)*value)/2
  
print(int(ans))
h,w,a,b = map(int,input().split())
s = [['0' for i in range(w)] for j in range(h)]
if (2*a > w and b != 0) or (2*b > h and a != 0):
    print('No')
    exit(0)
else:
    for i in range(h):
        cnt = i*a
        for _ in range(a):
            if cnt > w:
                cnt = 0
            s[i][cnt] = '1'
            cnt += 1
        print(''.join(map(str,s[i])))

### FIXED CODE ###

h,w,a,b = map(int,input().split())
s = [['0' for i in range(w)] for j in range(h)]
for i in range(h):
    for j in range(w):
        if (i < b and j >= a) or (i >= b and j < a):
            s[i][j] = '1'
    print(''.join(map(str,s[i])))
N=input()
A=input().split()
if(A in N):
  print("YES")
else:
  print("NO")

### FIXED CODE ###

S,T=input().split()
A,B=input().split()
U=input()
if(str(S)==str(U)):
  A=int(A)-1
if(str(T)==str(U)):
  B=int(B)-1
print(str(A)+' '+str(B))
n=int(input())
a=list(map(int,input().split()))
sum=0
for i in range(n):
  sum=sum+1/a[i]
print(1/ans)



### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
sum=0
for i in range(n):
  sum=sum+1/a[i]
print(1/sum)
a = list(map(int,input().split()))

print("A{}C".format(a[1]))

### FIXED CODE ###

a = list(map(str,input().split()))

print("A{}C".format(a[1][0]))
from itertools import product
n, m, x = list(map(int, input().split()))
cl = [0] * n
al = [[]*m for _ in range(n)]
for i in range(n):
    tmp = list(map(int, input().split()))
    cl[i] = tmp[0]
    al[i] = tmp[1:]


def dfs(status, book):
    for i in range(m):
        status[i] += book[i]
    return status


ans = 10**10
for bit in product([0, 1], repeat=n):
    # print(bit)
    status = [0]*n
    money = 0
    for i, b in enumerate(list(bit)):
        if b == 1:
            status = dfs(status, al[i])
            money += cl[i]
    flag = True
    for i in range(n):
        if status[i] >= x:
            continue
        else:
            flag = False
    if flag:
        ans = min(ans, money)
if ans == 10**10:
    print(-1)
    exit()
print(ans)


### FIXED CODE ###

from itertools import product
n, m, x = list(map(int, input().split()))
cl = [0] * n
al = [[]*m for _ in range(n)]
for i in range(n):
    tmp = list(map(int, input().split()))
    cl[i] = tmp[0]
    al[i] = tmp[1:]


def dfs(status, book):
    for i in range(m):
        status[i] += book[i]
    return status


ans = 10**10
for bit in product([0, 1], repeat=n):
    # print(bit)
    status = [0]*m
    money = 0
    for i, b in enumerate(list(bit)):
        if b == 1:
            for k in range(m):
                status[k] += al[i][k]
            money += cl[i]
    flag = True
    for i in range(m):
        if status[i] >= x:
            continue
        else:
            flag = False
    if flag:
        ans = min(ans, money)
if ans == 10**10:
    print(-1)
else:
    print(ans)
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
heights = sorted([int(input() for _ in range(N)])
ans = float('inf')
for i in range(N - K + 1):
    if abs(heights[i] - heights[i + K - 1]) < ans:
        ans = abs(heights[i] - heights[i + K - 1])
print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
heights = sorted([int(input()) for _ in range(N)])
ans = max(heights)
for i in range(N - K + 1):
    if abs(heights[i] - heights[i + K - 1]) < ans:
        ans = abs(heights[i] - heights[i + K - 1])
print(ans)