Problem:
 Score : 1300 points    Problem Statement Takahashi has a string S of length N consisting of lowercase English letters.
On this string, he will perform the following operation K times:   Let T be the string obtained by reversing S , and U be the string obtained by concatenating S and T in this order.  Let S' be some contiguous substring of U with length N , and replace S with S' .   Among the strings that can be the string S after the K operations, find the lexicographically smallest possible one.      Constraints  1 \leq N \leq 5000  1 \leq K \leq 10^9  |S|=N  S consists of lowercase English letters.         Input Input is given from Standard Input in the following format:  N  K  S       Output Print the lexicographically smallest possible string that can be the string S after the K operations.        Sample Input 1 5 1
bacba      Sample Output 1 aabca  When S= bacba , T= abcab , U= bacbaabcab , and the optimal choice of S' is S'= aabca .       Sample Input 2 10 2
bbaabbbaab      Sample Output 2 aaaabbaabb

Solution (Python):
N,K=map(int,input().split())
S=input()
s=[S[i] for i in range(N)]
m=min(s)

if K>=14:
    ans=[m for i in range(N)]
    print("".join(ans))
elif K==1:
    res=["z"]*N
    s=s+s[::-1]
    for i in range(N+1):
        test=s[i:i+N]
        if res>test:
            res=test
    print("".join(res))
else:
    cnt=0
    for i in range(N-1,-1,-1):
        if s[i]==m:
            cnt+=1
        else:
            break
    res=cnt
    for i in range(N-1,-1,-1):
        if cnt<N:
            if s[i]==m:
                cnt+=1
            else:
                cnt=0
        else:
            if s[i]!=m:
                cnt=0
        res=max(res,cnt)

    test=[]
    cnt=0
    for i in range(N-1,-1,-1):
        if s[i]==m:
            cnt+=1
        else:
            break
    if res*2**(K-1)>=N:
        ans=[m]*N
        exit(print("".join(ans)))
    check=N-res*2**(K-1)
    if cnt==res:
        test.append(N-1)
    for i in range(N-1,-1,-1):
        if cnt<N:
            if s[i]==m:
                cnt+=1
            else:
                cnt=0
        else:
            if s[i]!=m:
                cnt=0
        if cnt==res:
            test.append(N-1+N-i)
    result=[]
    for t in test:
        temp=s+s[::-1]
        temp=temp[t+1-res-check:t+1-res]
        temp=temp[::-1]
        result.append(temp)
    ans1=min(result)
    ans=[m]*res*2**(K-1)+ans1
    print("".join(ans))

Solution (Python):
n, k = map(int, input().split())
s = input()
rev_s = s + s[::-1]
mido = "z" * n
for i in range(n + 1):
    if mido > rev_s[i:i + n]:
        mido = rev_s[i:i + n]
ind = float("inf")
for i in range(n):
    if mido[i] != mido[0]:
        if i < ind:
            ind = i
ans = ind * (2 ** min(k - 1, 20))
print((mido[0] * ans + mido[ind:ind + n - ans])[:n])

Solution (Python):
n,k=map(int,input().split())
s=input()
slist=list(s)
num=0
for i in range(17):
    if 2**num>=n:
        num+=1
        break
    num+=1
if k>=num:
    slist.sort()
    ans=slist[0]*n
    print(ans)
else:
    for i in range(n):
        slist.append(slist[n-1-i])
    s1=[]
    for i in range(n+1):
        s1.append(slist[i:i+n])
    s1.sort()
    sstr=s1[0]
    ss2=""
    for i in range(n):
        ss2+=sstr[i]
    s3=sstr[0]
    num10=1
    for i in range(n-1):
        if s3!=sstr[i+1]:
            break
        else:
            num10+=1
    s2=""
    for i in range(n):
        s2+=sstr[-1-i]
    slist.sort()
    num=min((2**(k-1))*num10,n)
    num2=n-num
    ans=slist[0]*num
    ans+=ss2[num10:num10+num2]
    print(ans)

Solution (Python):

"""

https://atcoder.jp/contests/agc037/tasks/agc037_e

辞書順最小の文字をAとする
できるだけAが先頭にたくさん並ぶようにしたい

XAYのとき
XAYYAX　となる。これが最後の場合はAを先頭にして取るのがよい
そうでなければ一番後ろがAになるようにとるのが正解？

3なら
YYA → YYAAYY
YAA → YAAAAY
AAA → …

と、Kが5000回以上あるなら絶対全部Aにできる
実際は、Aの長さは倍倍に増えていくのでlog5000回ぐらいで全部Aにできる

Aとして選ぶべき場所は、最長ならそれ
最長が複数ある場合、それ以降の並びが辞書順最小のモノを選ぶべき

実装が面倒くさい系だな…

"""

import sys
N,K = map(int,input().split())
S   = input()

if K == 1:

    u = S + S[::-1]
    
    lis = []
    for i in range(N+1):
        lis.append(u[i:i+N])
    lis.sort()
    print (lis[0])
    sys.exit()

else:

    u = S + S[::-1]
    
    lis = []
    for i in range(N+1):
        lis.append(u[i:i+N])
    lis.sort()

    SR = lis[0]
    S  = lis[0][::-1]

    LL = 0
    for i in range(1,N):
        if SR[i] != SR[i-1]:
            LL = i
            break
    else:
        LL = N

    for i in range(2,K+1):

        u = S + S[::-1]
        
        SR = u[N-LL:2*N-LL]
        S  = SR[::-1]
        LL *= 2

        if LL >= N:
            break

    print (SR)

Solution (Python):
n, k = map(int, input().split())
s = input()
m = min(s)
for p in range(k):
    u = s + s[::-1]
    l = []
    cnt = 0
    idx = 0
    for i in range(n * 2):
        if u[i] == m:
            if cnt == 0:
                idx = i
            cnt += 1
        else:
            if cnt > 0:
                l.append((cnt, idx))
                cnt = 0
    if cnt > 0:
        l.append((cnt, idx))
    a, j = max(l)
    if a >= n:
        print(m * n)
        exit(0)
    for c, i in l:
        if i <= n and c == a:
            s = min(s, u[i:i + n])
    s = s[::-1]
print(s[::-1])

Solution (Python):
n, k = map(int, input().split())
s = input()
m = min(s)
for p in range(k):
    u = s + s[::-1]
    l = []
    cnt = 0
    idx = 0
    for i in range(n * 2):
        if u[i] == m:
            if cnt == 0:
                idx = i
            cnt += 1
        else:
            if cnt > 0:
                l.append((cnt, idx))
                cnt = 0
    if cnt > 0:
        l.append((cnt, idx))
    a, j = max(l)
    if a >= n:
        print(m * n)
        exit(0)
    for c, i in l:
        if i <= n and c == a:
            s = min(s, u[i:i + n])
    s = s[::-1]
print(s[::-1])

Solution (Python):
n,k=map(int,input().split())
k=min(k,20)
S=list(input())
for i in range(n):
  S[i]=ord(S[i])-97
T=S[::-1]
U=S+T
f=0
for i in range(26):
  A=[]
  for j in range(2*n):
    if U[j]==i:
      f=1
      A.append(j)
  if f==1:
    c=i
    break
B=[]
a=1
for i in range(1,len(A)):
  if A[i]==A[i-1]+1:
    a=a+1
    if A[i]>=n:
      B.append([a,A[i]])
  else:
    a=1
    if A[i]>=n:
      B.append([a,A[i]])
C=[]
b=max(B[i][0] for i in range(len(B)))
for i in range(len(B)):
  if B[i][0]==b:
    C.append(B[i][1])
if b*2**(k-1)>=n:
  for i in range(n):
    print(chr(97+c),end="")
  print()
  exit()
Ans=[]
d=n-b*2**(k-1)
for i in range(len(C)):
  AAns=U[C[i]-d-b+1:C[i]-b+1]
  Ans.append(AAns[::-1])
Ans.sort()
for i in range(b*2**(k-1)):
  print(chr(97+c),end="")
for i in range(n-b*2**(k-1)):
  print(chr(97+Ans[0][i]),end="")
print()

Solution (Python):
from math import floor, log
inpl = lambda: list(map(int,input().split()))
N, K = inpl()
S = input()
U = S + S[::-1]
Sp = sorted([ U[i:i+N] for i in range(N+1)])[0]
n = 0
while Sp[n] == Sp[0]:
    n += 1

if K > int(floor(log(N/n)/log(2))) + 1:
    print(Sp[0]*N)
else:
    m = n * (2**(K-1))
    if m >= N:
        print(Sp[0]*N)
    else:
        print(Sp[0]*m + Sp[n:n+N-m])

Solution (Python):
n,k=map(int,input().split())
s=input()
r=range(n)
u=min((s+s[::-1])[i:]for i in r)
for i in r:u[i]==u[0]or exit(print((u[0]*min(i<<k-1,n)+u[i:])[:n]))

Solution (Python):
n,k=map(int,input().split())
s=input()
r=range(n)
u=min((s+s[::-1])[i:]for i in r)
i=min(i for i in r if u[i]!=u[0])
print((u[0]*min(i<<k-1,n)+u[i:])[:n])

Solution (Python):
n,k=map(int,input().split())
s=input()
u=min((s+s[::-1])[i:]for i in range(n+1))
i=min(i for i in range(n)if u[i]!=u[0])
print((u[0]*min(i<<k-1,n)+u[i:])[:n])

Solution (Python):
n,k=map(int,input().split())
s=input()
u=s+s[::-1]
u=min((u[i:i+n])for i in range(n))
for i in range(n):
  if u[i]!=u[0]:break
c=i
for _ in range(k-1):
  c*=2
  if c>n:break
print((u[0]*c+u[i:])[:n])

Solution (Python):
n,k=map(int,input().split())
s=input()
j=1
cnt=1
while j<n:
    j*=2
    cnt+=1
if k>=cnt:print(min(s)*n)
else:
    if k==1:
        minstr=s+s[::-1]
    for i in range(k-1):
        s=s+s[::-1]
        minstr=s[:n]
        for j in range(n+1):
            if s[j:j+n]<minstr:
                minstr=s[j:j+n]
        s=minstr[::-1]
    if k>=2:
        minstr=minstr[::-1]+minstr
    ans=minstr[:n]
    for i in range(n+1):
        if ans > minstr[i:i+n]:
            ans=minstr[i:i+n]
    print(ans)

Solution (Python):
n,k=map(int,input().split())
s=input()
t=s[::-1]
u="".join([s,t])
ls=[]
for i in range(n):
  ls.append(u[i:i+n])
ls.sort()
k-=1
x=ls[0]
cnt=1
for i in range(1,n):
  if x[0]==x[i]:
    cnt+=1
  else:
    break
if cnt*2**k<n:
  y=n-cnt*2**k
  print(x[0]*(cnt*2**k)+x[cnt:y+cnt])
else:
  print(x[0]*n)

Solution (Python):
N, K = map(int,input().split())
S = input()

lex_min = "z"
for char in S:
  lex_min = min(char, lex_min)

U = S + S[::-1]

L = 0
L_max = 0
for i in range(N << 1):
  if U[i] == lex_min:
    L_max += 1
  else:
    L = max(L, L_max)
    L_max = 0
L = max(L, L_max)

if (1 << (K - 1)) * L >= N:
  print(lex_min * N)
else:
  candidates = []
  n = (1 << (K - 1)) * L
  for i in range(N, N << 1):
    if U[i-L+1:i+1] == L * lex_min:
      cand = n * lex_min + U[i-N+n-L+1:i-L+1][::-1]
      candidates.append(cand)
      
  print(min(candidates))

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,K = map(int,readline().split())
S = read().rstrip().decode('utf-8')

if K > 30:
    K = 30

SS = S + S[::-1]

if K == 1:
    answer = min(SS[i:i+N] for i in range(N+1))
    print(answer)
    exit()

min_ch = min(S)
run_len = [0] * len(SS)
for i,x in enumerate(SS):
    if x == min_ch:
        run_len[i] = run_len[i-1] + 1

max_len = max(run_len)
I = [i for i,x in enumerate(run_len[N-1:],N-1) if x == max_len]

if (max_len << (K-1)) >= N:
    answer = min_ch * N
    print(answer)
    exit()

L = max_len << (K-1)
cand = []
for i in I:
    T = SS[i-N+1:i+1]
    cand.append(T[-max_len-1:-max_len-(N-L)-1:-1])

answer = min_ch * L + min(cand)
print(answer)

Solution (Python):
n, k=map(int, input().split())
s=input()
u=s+s[::-1]
ans=min(u[i:i+n] for i in range(n+1))
c=ans[0]
i=min(i for i in range(n) if c!=ans[i])
h=(i<<min(k-1, 13))
ret=(h*c+ans[i:i+n-h])[:n]
print(ret)

Solution (Python):
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)))

Solution (Python):
n,k=map(int,input().split())
s=input()
u=s+s[::-1]
t=min(u[i:i+n]for i in range(n+1))
h=t[0]
i=min(i for i in range(n)if t[i]!=h)
j=i<<min(k-1,13)
print((h*j+t[i:i+n-j])[:n])

Solution (Python):
n, k = map(int, input().split())
s = input()
u = s + s[::-1]
t = min(u[i:i + n] for i in range(n + 1))
h = t[0]
i = min(i for i in range(n) if t[i] != h)
j = i << min(k - 1, n.bit_length())
print((h * j + t[i:i + n - j])[:n])

Solution (Python):
n, k = map(int, input().split())
s = input()
u = s + s[::-1]
t = min(u[i:i + n] for i in range(n + 1))
i, h = 0, t[0]
for i in range(n):
    if t[i] != h:
        break
j = i
for _ in range(k - 1):
    j <<= 1
    if j >= n:
        print(h * n)
        break
else:
    print(h * j + t[i:i + n - j])

Solution (Python):
def solve(n, k, s):
    u = s + s[::-1]
    t = min(u[i:i + n] for i in range(n + 1))
    i, h = 0, t[0]
    for i, c in enumerate(t):
        if c != h:
            break
    j = i
    for _ in range(k - 1):
        j <<= 1
        if j >= n:
            return h * n
    return h * j + t[i:i + n - j]


n, k = map(int, input().split())
s = input()
print(solve(n, k, s))

Solution (Python):
N, K = map(int, input().split())
S = input()
T = S[::-1] 
U = S + T
D = []
for i in range(N):
  D.append(U[i:i+N])
D.sort()
B = D[0]
for i in range(N):
  if B[i] != B[0]:
    break
if i * 1 << (K - 1) > N:
  print(B[0] * N)
else:
  print((B[0] * (i * (1 << (K - 1))) + B[i:])[:N])

Solution (Python):
n,k=map(int,input().split())
s=list(input())
l=0
c=0
for i in range(n):
    if s[i]==min(s):
        c+=1
        l=max(l,c)
    else:
        c=0
s.reverse()
if (2**(k-1))*l>n:
    print(min(s)*n)
else:
    for i in range(min(k,13)):
        t=list(reversed(s))
        u=t+s
        uu=u[:n]
        for j in range(1,n+1):
            x=u[j:j+n]
            if uu>x:
                uu=x
        s=uu
    print("".join(s))

Solution (Python):
n,k=map(int,input().split())
s=list(input())
l=0
c=0
for i in range(n):
    if s[i]==min(s):
        c+=1
        l=max(l,c)
    else:
        c=0
import sys
input=sys.stdin.readline
s.reverse()
if (2**(k-1))*l>n:
    print(min(s)*n)
else:
    for i in range(min(k,13)):
        t=list(reversed(s))
        u=t+s
        uu=u[:n]
        for j in range(1,n+1):
            x=u[j:j+n]
            if uu>x:
                uu=x
        s=uu
    print("".join(s))

Solution (Python):
N, K = map(int, input().split())
S = input()
SS = S + S[::-1]
D = []
for i in range(N):
  D.append(SS[i:i+N])
D.sort()
B = D[0]
for i in range(N):
  if B[i] != B[0]:
    break
if i * 1 << (K - 1) > N:
  print(B[0] * N)
else:
  print((B[0] * (i * (1 << (K - 1))) + B[i:])[:N])

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

n, k = map(int, input().split())
s = str(input())

u = s + s[::-1]
ss = s

if n < k**2:
    smallest = sorted(s)[0]
    print(smallest * n)

else:
    times = min(n, k)
    for i in range(times):
        for j in range(n):
            part = u[j:j+n]
            if part < ss:
                ss = part
        s = ss
        u = s[::-1] + s
    print(s)

Solution (Python):
n, k = map(int, input().split())
s = input()

if k > 5000 * 26:
    k = 5000 * 26

if k != 1:
    for i in range(k - 1):
        sList = []
        t = (s[::-1])
        u = s + t
        for j in range(0, n+1):
            sList.append((u[j:(j + n)])[::-1])
        sList.sort()
        if s == sList[0][::-1]:
            break
        s = sList[0][::-1]


for i in range(1):
    sList = []
    t = (s[::-1])
    u = s + t
    for j in range(0, n+1):
        sList.append(u[j:(j + n)])
    sList.sort()
    s = sList[0]

print(s)

Solution (Python):
N, K = map(int,input().split())
S = input()

aaaa = False




if K >= 15:
    aaaa = True
elif 2 ** K >= N:
    aaaa = True


if aaaa:
    print(min(S)*N)
    exit()

def get_last_dict(s_str):
    U = s_str + s_str[::-1]
    c = min(s_str)
    p = U.index(c)
    minindex = p
    p += 1
    while p <= N:
        if U[p] == c:
            if check_normal_dict(U, minindex, p):
                minindex = p
        p += 1
    return U[minindex:minindex+N]


def check_normal_dict(u, pointer1, pointer2):
    for i in range(N):
        if u[pointer1 + i] > u[pointer2 + i]:
            return True
        elif u[pointer1 + i] < u[pointer2 + i]:
            return False
    return False

S = get_last_dict(S)

if K == 1:
    print(S)
else:
    count = 0
    for c in S:
        if c == S[0]:
            count += 1
        else:
            break
    if count * (2 ** (K - 1)) >= N:
        print(S[0] * N)
    else:
        S = S[0] * (count * ((2 ** (K - 1)) - 1)) + S
        print(S[0:N])

Solution (Python):
n,k=map(int,input().split())
s=input()
d=s+s[::-1]
d=d[::-1]
r=d[:n]
e=d[:n]
for i in range(n):
    e=e[1:]+d[n+i]
    r=min(r,e)
t=1
qo=r[0]
for i in range(1,n):
    if qo==r[i]:
        t+=1
    else:
        break
r=r[::-1]
for i in range(k-1):
    p=r+r[n-t:]
    p=p[::-1]
    p=p[:n]
    if r==p:
        break
    else:
        r=p[::-1]
        t+=t
print(r[::-1])

Solution (Python):
N,K = map(int,input().split())
S = input()


if N < 2**K:
    S_young = sorted(list(S))[0]
    print(S_young*N)
    
else:
    word=S
    S=S+S[::-1]
    for i in range(K):
        for j in range(N-1):
            if word > S[1+j:1+j+N]:
                word = S[1+j:1+j+N]
        S = word[::-1]+word
    print(word)

Solution (Python):
str = input()
a = str.split(" ")
n = (int)(a[0])
k = (int)(a[1])
str = input()
before = ""
for ii in range(k-1):
  s = str + str[::-1]
  s1 = s[0:n]
  for i in range(1,n+1):
    s2 = s[i:n+i]
    if(s1>s2):
      s1 = s2
  str = s1[::-1]
  if(before==str):
    break
  before = str

s = str + str[::-1]
s1 = s[0:n]
for i in range(1,n+1):
  s2 = s[i:n+i]
  if(s1>s2):
    s1 = s2
print(s1)

Solution (Python):
n,k = (int(x) for x in input().split())
s = str(input())
slist = sorted(list(s))
if len(slist)-1<k:
  ans = ""
  for t in slist:
    ans += slist[0]
  print(ans)
else:
  ss = s + s[::-1]
  
  lens = len(s)
  rev = []
  for i in range(k-1):
    for x in range(lens+1):
      r = ss[x:lens+x]
      rev.append(r[::-1])
    sortrev = sorted(rev)
    tmp = sortrev[0]
    ss = tmp[::-1]+tmp
    
    
    rev = []
  for x in range(lens+1):
    r = ss[x:lens+x]
    rev.append(r)
  sortrev = sorted(rev)
  print(sortrev[0])