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

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

MOD = 10 ** 9 + 7

ans = 0
combinations = list()
for j, i in enumerate(range(k - 1, n)):
    if i == (k - 1):
        combinations.append(1)
    else:
        combinations.append(combinations[-1] * i // (i - k + 1))
    # print(i, 'C', k - 1, '=', combinations[-1])

# print(combinations)
# print(A)
combinations = combinations[::-1]
for j, i in enumerate(range(k - 1, n)):
    ans += (A[-j - 1] * combinations[j] % MOD)

for j, i in enumerate(range(k - 1, n)):
    ans -= (A[j] * combinations[j] % MOD)
    if ans < 0:
        ans = ans - (ans // MOD) * MOD

ans %= MOD
print(ans)


### FIXED CODE ###

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

MOD = 10 ** 9 + 7


def pow(a, n):
    if n == 0:
        return 1
    else:
        temp = pow(a, n // 2)
        if n % 2 == 0:
            return temp * temp % MOD
        else:
            return temp * temp * a % MOD
        
        
ans = 0
combinations = list()
for j, i in enumerate(range(k - 1, n)):
    if i == (k - 1):
        combinations.append(1)
    else:
        combinations.append(combinations[-1] * i * pow(i - k + 1, MOD - 2))
    combinations[-1] = combinations[-1] % MOD
    # print(i, 'C', k - 1, '=', combinations[-1])

# print(combinations)
# print(A)
combinations = combinations[::-1]
for j, i in enumerate(range(k - 1, n)):
    ans += (A[-j - 1] * combinations[j] % MOD)

for j, i in enumerate(range(k - 1, n)):
    ans -= (A[j] * combinations[j] % MOD)
    if ans < 0:
        ans = ans + (- ans // MOD + 1) * MOD

ans %= MOD
print(ans)
### BUGGY CODE ###

import sys
import heapq
import bisect

mod = 10**9+7
dd = ((-1,0),(1,0),(0,-1),(0,1))

def I(): return(int(sys.stdin.readline()))
def LI(): return([int(x) for x in sys.stdin.readline().split()])
def S(): return(sys.stdin.readline()[:-1])
def IR(n): return([I() for _ in range(n)])

def GCD(a,b):
    while b!=0:
        a,b = b,a%b
    return a

def LCM(a,b):
    return a * b // GCD(a,b)

def main():
    N,Q = LI()
    Child = [[] for _ in range(N)]
    tree = [False]*N
    tree[0] = True
    cur_tree = []
    for _ in range(N-1):
        a,b = LI()
        cur_tree.append([a-1,b-1])

    counter = [0] * N
    for _ in range(Q):
        p,x = LI()
        counter[p-1] += x

    while cur_tree:
        nxt_tree = []
        for a,b in cur_tree:
            if tree[a]:
                Child[a].append(b)
                counter[b] += counter[a]
                tree[b] = True
            elif tree[b]:
                Child[b].append(a)
                counter[a] += counter[b]
                tree[a] = True
            else:
                nxt_tree.append([a,b])
        cur_tree = [x for x in nxt_tree]

    r = [counter[i] for i in range(N)]

    return(" ".join(map(str,r)))

if __name__ == "__main__":
    print(main())


### FIXED CODE ###

import sys
import heapq
import bisect

mod = 10**9+7
dd = ((-1,0),(1,0),(0,-1),(0,1))

def I(): return(int(sys.stdin.readline()))
def LI(): return([int(x) for x in sys.stdin.readline().split()])
def S(): return(sys.stdin.readline()[:-1])
def IR(n): return([I() for _ in range(n)])

def GCD(a,b):
    while b!=0:
        a,b = b,a%b
    return a

def LCM(a,b):
    return a * b // GCD(a,b)

def main():
    N,Q = LI()
    node=[[] for _ in range(N)]
    flag = [True for _ in range(N)]
    for _ in range(N-1):
        a,b = LI()
        node[a-1].append(b-1)
        node[b-1].append(a-1)

    counter = [0] * N
    for _ in range(Q):
        p,x = LI()
        counter[p-1] += x

    cur = [[0,0]]
    while cur:
        nxt = []
        for a,c in cur:
            flag[a]=False
            counter[a]+=c
            for b in node[a]:
                if flag[b]:
                    nxt.append([b,counter[a]])
        cur = [x for x in nxt]

    r = [counter[i] for i in range(N)]

    return(" ".join(map(str,r)))

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

import math
from functools import lru_cache
from operator import mul
from functools import reduce

@lru_cache(maxsize=None)
def for_factorial(n):
    val = 1
    for i in range(2, n + 1):
        val = (val * i)
    return val



x, y = map(int, input().split())
mod = 1000000007
cnt = (x + y) // 3
if (x + y) % 3 != 0:
    print(0)
    exit()
m = min(x, y)
num_2 = m - cnt
num_1 = cnt - num_2
#print(cnt, num_1, num_2)
f_1 = for_factorial(num_1)
f_2 = for_factorial(num_2)
ans = for_factorial(cnt)
#print(ans, f_1, f_2)
f = f_1 * f_2
ans //= f
ans %= mod
print(ans)



### FIXED CODE ###

import math
from functools import lru_cache
from operator import mul
from functools import reduce


def cmb(n, r, mod):
    numerator = reduce(lambda x, y: x * y % mod, [n - r + k + 1 for k in range(r)])
    denominator = reduce(lambda x, y: x * y % mod, [k + 1 for k in range(r)])
    return numerator * pow(denominator, mod - 2, mod) % mod


def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


def my_factorial(n, mod):
    if n == 1:
        return 1
    return (n * my_factorial(n-1, mod)) % mod


@lru_cache(maxsize=None)
def for_factorial(n):
    val = 1
    for i in range(2, n + 1):
        val = (val * i)
    return val



x, y = map(int, input().split())
mod = 1000000007
cnt = (x + y) // 3
if (x + y) % 3 != 0:
    print(0)
    exit()
m = min(x, y)
num_2 = m - cnt
num_1 = cnt - num_2
ans = cmb(cnt, num_1, mod)
print(ans)
### BUGGY CODE ###

s = input()
sgn = 1
Q = int(input())
ans = []
for _ in range(Q):
  i = input()
  if i[0] == '1':
    sgn*=-1
  else:
    if i[2] == '1':
      ans.append([i[4], -sgn])
    else:
      ans.append([i[4], sgn])

if sgn == -1:
  s = s[::-1]
  for k in range(len(ans)):
    if ans[k][1] == -1:
      s = s + ans[k][0]
    else:
      s = ans[k][0] + s
else:
  for k in range(len(ans)):
    if ans[k][1] == 1:
      s = s + ans[k][0]
    else:
      s = ans[k][0] + s

print(s)

### FIXED CODE ###

s = input()
sgn = 1
Q = int(input())
L = '' #sgn=-1
R = '' #sgn=1
for _ in range(Q):
  i = input()
  if i[0] == '1':
    sgn*=-1
  else:
    if i[2] == '1':
      if sgn == 1:
        L += i[4]
      else:
        R += i[4]
    else:
      if sgn == 1:
        R += i[4]
      else:
        L += i[4]

if sgn == -1:
  s = s[::-1]
  R = R[::-1]
  print(R + s +L)
  
else:
  L = L[::-1]
  print(L + s + R)
### BUGGY CODE ###

import numpy as np
s = list(map(int, input().split()))
n=s[0]
a = np.array(list(map(int, input().split())))
s = list(map(int, input().split()))
q=s[0]
for i in range(q):
    s = list(map(int, input().split()))
    a=np.where(a==s[0],s[1],a)
    print(np.sum(a))


### FIXED CODE ###

import numpy as np
from collections import defaultdict

s = list(map(int, input().split()))
n=s[0]
a = np.array(list(map(int, input().split())))
s = list(map(int, input().split()))
q=s[0]
num=defaultdict(int)
ans=0

for i in a:
    num[i]+=1
    ans+=i

for i in range(q):
    s = list(map(int, input().split()))
    a=s[0]
    b=s[1]
    ans=ans-a*num[a]-b*num[b]
    num[b]=num[a]+num[b]
    ans = ans+b*num[b]
    num[a]=0
    print(ans)
### BUGGY CODE ###

import bisect
import copy
n=int(input())
a=list(map(int,input().split()))
a.sort()
ans=0
for i in range(n):
  for j in range(i+1,n):
    if i==j:
      continue
    b=copy.deepcopy(a)
    b.remove(a[i])
    b.remove(a[j])
    ans+=bisect.bisect_left(b,a[i]+a[j])-j+1
print(ans)

### FIXED CODE ###

import bisect
n=int(input())
a=list(map(int,input().split()))
a.sort()
ans=0
for i in range(n):
  for j in range(i+1,n):
    ans+=bisect.bisect_left(a,a[i]+a[j])-j-1
print(ans)
### BUGGY CODE ###

def main():
  import sys
  from heapq import heappush, heappop, heapify
  _int = int
  _min = min
  n = _int(input())
  a = [_int(e) for e in input().split()]
  b = [_int(e) for e in input().split()]
  result = 0
  finished = 0
  hq = [(-b[i], i) for i in range(n)]
  heapify(hq)
  while True:
    _, i = heappop(hq)
    if a[i] == b[i]:
      finished += 1
      continue
    if i == 0:
      j = b[n - 1] + b[1]
    elif i == n - 1:
      j = b[n - 2] + b[0]
    else:
      j = b[i - 1] + b[i + 1]
    k = b[i] - a[i]
    if len(hq) != 0:
      l = b[i] + hq[0][0]
      if l < k:
        k = l
    k //= j
    if k <= 0:
      k = 1
    b[i] -= j * k
    if a[i] > b[i]:
      print(-1)
      sys.exit()
    result += k
    if a[i] == b[i]:
      finished += 1
      if finished == n:
        print(result)
        sys.exit()
    else:
      heappush(hq, (-b[i], i))
main()

### FIXED CODE ###

def main():
  import sys
  _int = int
  n = _int(input())
  a = [_int(e) for e in input().split()]
  b = [_int(e) for e in input().split()]
  result = 0
  q = [i for i in range(n) if b[i] != a[i]]
  while len(q) != 0:
    nq = []
    c = 0
    for i in q:
      if i == 0 or i == n - 1:
        j = b[(n + i - 1) % n] + b[(n + i + 1) % n]
      else:
        j = b[i - 1] + b[i + 1]
      if j > b[i] - a[i]:
        nq.append(i)
        continue
      c += 1
      k = (b[i] - a[i]) // j
      result += k
      b[i] -= j * k
      if a[i] != b[i]:
        nq.append(i)
    if c == 0 and len(nq) != 0:
      print(-1)
      sys.exit()
    q = nq
  print(result)
main()
### BUGGY CODE ###

n, q = map(int, input().split())
queue = []
for i in range(n):
    name, time = input().split()
    queue.append({"name": name, "time": int(time)})
t = 0
while len(queue) != 0:
    #print([queue[i]["time"] for i in range(len(queue))])
    if queue[0]["time"] <= q:
        t += queue[0]["time"]
        name = queue[0]["name"]
        queue = queue[1:]
        print("{} {}".format(name, t))
    else:
        if len(queue) != 1:
            queue = queue[1:] + \
                [{"name": queue[0]["name"], "time":queue[0]["time"] - q}]
            t += q
        else:
            queue[0] = {"name": queue[0]["name"], "time": queue[0]["time"] - q}
            t += q



### FIXED CODE ###

from collections import deque
n, q = map(int, input().split())
queue = deque()
for i in range(n):
    name, time = input().split()
    queue.append({"name": name, "time": int(time)})
t = 0
while len(queue) != 0:
    #print([queue[i]["time"] for i in range(len(queue))])
    head = queue.popleft()
    if head["time"] <= q:
        t += head["time"]
        name = head["name"]
        print("{} {}".format(name, t))
    else:
        queue.append({"name": head["name"], "time": head["time"] - q})
        t += q
### BUGGY CODE ###

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

#hyouten = []

score = 1
for i in range(k):
    score*=a[i]

for i in range(n-k+1):

    
    if i>0:
        score_old = score
        score = score // a[i-1] * a[i+k-1]
        
        if score >score_old:
            print("Yes")
        else:
            print("No")
#    hyouten.append(score)

### FIXED CODE ###

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

#hyouten = []


for i in range(n-k+1):

    
    if i>0:
        score_old = a[i-1]
        score = a[i+k-1]
#        print(score_old,score)
        if score >score_old:
            print("Yes")
        else:
            print("No")
### BUGGY CODE ###

N = int(input())
A = [int(a) for a in input().split()]
s = set(A)
x = [0] * N

for i in s:
    x[i-1] += A.count(i)

for i in x:
    print(i)


### FIXED CODE ###

N = int(input())
A = [int(a) for a in input().split()]
x = [0] * N

for i in A:
    x[i-1] += 1

for i in x:
    print(i)
### BUGGY CODE ###

R,G,B,N=map(int,input().split())
ans=0
for i in range(N+1):
    for j in range(N+1):
        if (N-(R*i+G*j))%B==0 and N-(R*i+G*j) >=0:
            ans+=1
        
print(ans)

### FIXED CODE ###

def solve():
    R,G,B,N=map(int,input().split())
    ans=0
    for i in range(N+1):
        for j in range(N+1):
            tmp=N-(R*i+G*j)
            if tmp>=0 and tmp%B==0:
                ans+=1
    print(ans)

solve()
### BUGGY CODE ###

n = int(input())

ans = 0
for i in range(1, n):
    ans += i

print(ans)


### FIXED CODE ###

n = int(input())

print(n * (n - 1) //2)
### BUGGY CODE ###

p = 1

n = int(input())

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

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

### FIXED CODE ###

import math

N = int(input())
print(math.factorial(N)%(10**9+7))
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
R = [0] * (N + 1)
P = [1] * (N + 1)
mod = 10 ** 9 + 7

def power(x, y):
    if y == 0:
        return 1
    elif y == 1: 
        return x % mod
    elif y % 2 == 0: 
        return power(x, y//2)**2 % mod
    else: 
        return power(x, y//2)**2 * x % mod

def rev(a):
    return power(a, mod - 2)
    
for n in range(N + 1):
    R[n] = R[n - 1] + rev(n)
    if n != 0:
        P[n] = P[n - 1] * n

res = 0
for i in range(N):
    res += ((R[i + 1] + R[N - i] - 1) % mod * A[i] * P[N]) % mod

print(res % mod)


### FIXED CODE ###

import numpy as np
N = int(input())
A = list(map(int, input().split()))
R = np.zeros(N + 1, dtype="int64")
P = np.ones(N + 1, dtype="int64")
mod = 10 ** 9 + 7

def rev(a):
    return pow(a, mod - 2, mod)
    
for n in range(N + 1):
    r = rev(n)
    R[n] = (R[n - 1] + r) % mod
    if n != 0:
        P[n] = (P[n - 1] * n) % mod

C = [(R[j] + R[N - j + 1] - 1) % mod for j in range(1, N + 1)]

res = 0
for i in range(N):
    res = (res + (A[i] * C[i]) % mod) % mod

print(res * P[N] % mod)
#print((sum([a * c % mod for a, c in zip(C, A)]) * P[N]) % mod)
### BUGGY CODE ###

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

ans = 0
while n >= 1 and m >= 2:
  ans += 1
  n -= 1
  m -= 2
if m >= 4:
  ans += m//4
print(ans)

### FIXED CODE ###

n,m = map(int, input().split())
ans = 0
if m >= 2 * n: 
    ans += n
    m -= 2 * n
    ans += m // 4
else: ans += m // 2
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import numpy as np

H, W = map(int, input().split())
S = [input() for x in range(H)]

L = np.zeros([H, W], dtype=int)
R = np.zeros([H, W], dtype=int)
U = np.zeros([H, W], dtype=int)
D = np.zeros([H, W], dtype=int)
for h in range(H):
    for w in range(W):
        if S[h][w] != '#':
            if w == 0:
                L[h, w] = 1
            else: L[h, w] = L[h][w-1] + 1
            if h == 0:
                U[h, w] = 1
            else: U[h, w] = U[h-1][w] + 1
        else:
            L[h, w] = 0
            U[h, w] = 0

for h in range(H-1, -1, -1):
    for w in range(W-1, -1, -1):
        if S[h][w] != '#':
            if w == W-1:
                R[h, w] = 1
            else: R[h, w] = R[h][w+1] + 1
            if h == H-1:
                D[h, w] = 1
            else: D[h, w] = D[h+1][w] + 1
        else:
            R[h, w] = 0
            D[h, w] = 0

L = np.array(L)
R = np.array(R)
U = np.array(U)
D = np.array(D)
print(np.max(L+R+U+D)-3)

### FIXED CODE ###

# -*- coding: utf-8 -*-
import numpy as np

H, W = map(int, input().split())
S = [input() for x in range(H)]

L = np.zeros([H, W], dtype=int)
R = np.zeros([H, W], dtype=int)
U = np.zeros([H, W], dtype=int)
D = np.zeros([H, W], dtype=int)

S_ = np.zeros([H, W], dtype=int)
for h in range(H):
    for w in range(W):
        if S[h][w] == '#': S_[h, w] = 0
        else: S_[h, w] = 1
L[:, 0] = S_[:, 0]
for w in range(1, W):
    L[:, w] = (L[:, w-1] + 1) * S_[:, w]
R[:, W-1] = S_[:, W-1]
for w in range(W-2, -1, -1):
    R[:, w] = (R[:, w+1] + 1) * S_[:, w]
U[0] = S_[0]
for h in range(1, H):
    U[h] = (U[h-1] + 1) * S_[h]
D[H-1] = S_[H-1]
for h in range(H-2, -1, -1):
    D[h] = (D[h+1] + 1) * S_[h]

L = np.array(L)
R = np.array(R)
U = np.array(U)
D = np.array(D)
print(np.max(L+R+U+D)-3)
### BUGGY CODE ###

from heapq import *
INF = 1e10
respostas = []

def floyd(n):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])

N,M,L = map(int,input().split())

d = [[INF]*N for i in range(N)]

for x in range(M):
    a,b,w = map(int,input().split())
    d[a-1][b-1] = w
    d[b-1][a-1] = w
    d[a-1][a-1] = 0
    d[b-1][b-1] = 0


floyd(N)
grafo2 = [[INF] * N for i in range(N)]

for x in range(len(d)):
    for y in range(len(d[x])) :
        if d[x][y] <= L:
            grafo2[x][y] = 1
            grafo2[y][x] = 1



for k in range(N):
    for i in range(N):
        for j in range(N):
            grafo2[i][j] = min(grafo2[i][j], grafo2[i][k] + grafo2[k][j])

query = int(input())

for x in range(query):
    s,t = map(int,input().split())
    if grafo2[s-1][t-1] == INF:
        respostas.append(-1)
    else:
        respostas.append(grafo2[s-1][t-1] - 1)

for x in respostas:
    print(x)


### FIXED CODE ###

from heapq import *
INF = 1e10

def floyd(n):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]

N,M,L = map(int,input().split())

d = [[INF]*N for i in range(N)]

for x in range(M):
    a,b,w = map(int,input().split())
    d[a-1][b-1] = w
    d[b-1][a-1] = w

floyd(N)

grafo2 = [[INF] * N for i in range(N)]

for x in range(N):
    for y in range(N) :
        if d[x][y] <= L:
            grafo2[x][y] = 1

for k in range(N):
    for i in range(N):
        for j in range(N):
            if grafo2[i][j] > grafo2[i][k] + grafo2[k][j]:
                grafo2[i][j] = grafo2[i][k] + grafo2[k][j]

query = int(input())

for x in range(query):
    s,t = map(int,input().split())
    if grafo2[s-1][t-1] == INF:
        print(-1)
    else:
        print(grafo2[s-1][t-1] - 1)
### BUGGY CODE ###

A, B, N = map(int, input().split())
i = N

while i % B != 0:
  i = i - 1
  
i = i - 1
if i < 0:
  ans = (A * N) // B - A * (N // B)
else:
  ans = (A * i) // B - A * (i // B)
  
print(ans)

### FIXED CODE ###

A, B, N = map(int, input().split())
i = (N // B) * B
  
i = i - 1
if i < 0:
  ans = (A * N) // B - A * (N // B)
else:
  ans = (A * i) // B - A * (i // B)
  
print(ans)
### BUGGY CODE ###

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

tem=0
ans=0

for i in range(n-k+1):
    tem=0
    if i>1 and p[i-1]>p[i+k-1]:
        continue
    for j in range(k):
        tem=tem+(p[i+j]/2)+1/2
    ans=max(ans,tem)

print(ans)

### FIXED CODE ###

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

tem=0
ans=0

for i in range(k):
    ans=ans+(p[i]/2)+1/2
    tem=tem+(p[i]/2)+1/2

for i in range(1,n-k+1):
    fi=p[i-1]/2 +1/2
    la=p[i+k-1]/2 +1/2
    tem=tem-fi+la
    ans=max(ans,tem)

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

N,A = map(int,input().split())
X = [int(x)-A for x in input().split()]

ans = 0
for i in range(2**N):
    tmp = 0 
    for j in range(N):
        if (i>>j)&1:
            tmp+=X[j]       
    if tmp==0:      
        ans += 1
print(ans-1)


### FIXED CODE ###

N,A = map(int,input().split())
X = [int(x)-A for x in input().split()]

z = 0 
dic = {}

for x in X:
    if x==0:
        z += 1
    else:
        dic[x] = dic.get(x,0) + 1
            
line = {}
line[0] = 1

for k in dic:    
    line_k = {}
    for i in range(dic[k]+1):
        line_k[k*i] = 1      
        for j in range(dic[k],dic[k]-i,-1):
            line_k[k*i] *= j
        for j in range(1,1+i):
            line_k[k*i] //= j
    line_tmp = {}
    for k_lk in line_k:
        for k_l in line:
            line_tmp[k_lk+k_l] = line_tmp.get(k_lk+k_l,0) + line_k[k_lk] * line[k_l]
    line = line_tmp.copy()
    
print(line[0] * (2**z) -1)
### BUGGY CODE ###

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

mod = 10**9 + 7

ans = 0
# 制約より、aはそれぞれ60桁以内で表せる
# i+1(=1,2,...,60)桁目についてそれぞれ考える
for i in range(60):
    k = 1 << i  # k = 100....00(2) = 2**i(10)
    cnt_1 = 0
    cnt_0 = 0

    for ai in a:
        if k & ai:
            cnt_1 += 1
        else:
            cnt_0 += 1
    # 1 XOR 0 = 1 となる個数 = cnt_1 * cnt_0
    ans += (k * cnt_1 * cnt_0) % mod

print(ans % mod)


### FIXED CODE ###

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

mod = 10**9 + 7

ans = 0
# 制約より、aはそれぞれ60桁以内で表せる
# i+1(=1,2,...,60)桁目についてそれぞれ考える
for i in range(60):
    k = 1 << i  # k = 100....00(2) = 2**i(10)
    cnt_1 = 0
    cnt_0 = 0

    for ai in a:
        if k & ai:
            cnt_1 += 1
        else:
            cnt_0 += 1
    # 1 XOR 0 = 1 となる個数 = cnt_1 * cnt_0
    ans += (k % mod * cnt_1 * cnt_0) % mod

print(ans % mod)
### BUGGY CODE ###

N,M,P = map(int,input().split())
E = []
for i in range(M):
  a,b,c=map(int,input().split())
  a-=1
  b-=1
  c=-c+P
  E.append([a,b,c])
  
def BellmanFord(s,g):
  #グラフの初期化
  inf=float("inf")
  dist=[inf for i in range(N)]
  dist[s]=0
  rout=[]
  
  #辺の緩和
  for i in range(N*N):
    for edge in E:
      if dist[edge[1]] > dist[edge[0]] + edge[2]:
        dist[edge[1]] = dist[edge[0]] + edge[2]
        if i==N*N-1 and edge[1]==g: return -1
  
  return max(0,-dist[g])
print(BellmanFord(0,N-1))

### FIXED CODE ###

N,M,P = map(int,input().split())
E = []
for i in range(M):
  a,b,c=map(int,input().split())
  a-=1
  b-=1
  c=-c+P
  E.append([a,b,c])
  
def BellmanFord(s,g):
  #グラフの初期化
  inf=float("inf")
  dist=[inf for i in range(N)]
  dist[s]=0
  rout=[]
  
  #辺の緩和
  for i in range(N):
    for edge in E:
      if dist[edge[1]] > dist[edge[0]] + edge[2]:
        dist[edge[1]] = dist[edge[0]] + edge[2]
        if i==N-1: dist[edge[1]]=-inf
  for i in range(N):
    for edge in E:
      if dist[edge[1]] > dist[edge[0]] + edge[2]:
        dist[edge[1]] = dist[edge[0]] + edge[2]
  if dist[g] == -inf:return -1
  return max(0,-dist[g])
print(BellmanFord(0,N-1))
### BUGGY CODE ###

from collections import deque
import sys


def input():
    return sys.stdin.readline()[:-1]


h, w = map(int, input().split())
grid = [input() for _ in range(h)]
cost = [[float("inf")] * w for _ in range(h)]
nb = [(-1, 0), (0, -1), (1, 0), (0, 1)]

q = deque()
for i in range(h):
    for j in range(w):
        if grid[i][j] == "#":
            q.append((i, j))
            cost[i][j] = 0

while q:
    x, y = q.popleft()
    for dx, dy in nb:
        nx = x + dx
        ny = y + dy
        if 0 <= nx and nx < h and 0 <= ny and ny < w and cost[nx][ny] == float("inf"):
            cost[nx][ny] = cost[x][y] + 1
            q.append((nx, ny))


print(max([max(c) for c in cost]))


### FIXED CODE ###

from collections import deque
 
H, W = map(int, input().split())
A = [input() for i in range(H)]
q = deque()
c = [[-1] * W for i in range(H)]
for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            q.append((i, j))
            c[i][j] = 0
D = [[0, 1], [1, 0], [0, -1], [-1, 0]]
while q:
    y, x = q.popleft()
    for dy, dx in D:
        ny, nx = y+dy, x+dx
        if 0 <= ny < H and 0 <= nx < W and c[ny][nx] == -1:
            q.append((ny, nx))
            c[ny][nx] = c[y][x]+1
print(max([max(l) for l in c]))
### BUGGY CODE ###

N,K=map(int,input().split())
S=list(input())
MIN=min(S)

def minimum(S):
    T=S+S[::-1]

    ANS=[]

    for i in range(N+1):
        ANS.append(T[i:i+N])

    return min(ANS)

def next(S):
    T=S+S[::-1]
    LIST=[]
    CL=[0]*2*N
    count=0

    for i in range(2*N):
        if T[i]==MIN:
            count+=1

        else:
            count=0

        CL[i]=count

    MAX=max(CL)
    LIST=[]

    for i in range(N-1,2*N):
        if CL[i]==MAX:
            LIST.append(T[i+1-N:i+1])

    return LIST

if K==1:
    print("".join(minimum(S)))

else:
    CAN=next(S)

    ANS=[]

    for c in CAN:
        for j in range(K-2):
            c=next(c)[0]

            if c==MIN*N:
                print("".join(c))
                sys.exit()

        ANS.append(minimum(c))

    print("".join(min(ANS)))


### FIXED CODE ###

import sys

N,K=map(int,input().split())
S=list(input())
MIN=min(S)

def minimum(S):
    T=S+S[::-1]

    ANS=[]

    for i in range(N+1):
        ANS.append(T[i:i+N])

    return min(ANS)

def next(S):
    T=S+S[::-1]
    LIST=[]
    CL=[0]*2*N
    count=0

    for i in range(2*N):
        if T[i]==MIN:
            count+=1

        else:
            count=0

        CL[i]=count

    MAX=max(CL)
    LIST=[]

    for i in range(N-1,2*N):
        if CL[i]==MAX:
            LIST.append(T[i+1-N:i+1])

    return LIST,MAX

def next2(S,x):
    return [MIN]*x+S[x:][::-1]

if K==1:
    print("".join(minimum(S)))

else:
    CAN,MAX=next(S)

    if (MAX<<(K-1))>=N:
        print(MIN*N)
        sys.exit()

    ANS=[]

    for c in CAN:

        ANS.append(next2(c,MAX*((1<<(K-1))-1)))

    print("".join(min(ANS)))