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



Sample input:
5 1
bacba


Sample output:
aabca

Submission status: Time Limit Exceeded

Solution code:
import binascii
n, k = [int(x) for x in input().split()]
s = input()

candidates = [s]
visited = set()
ret = ""


def get_smaller(target, current):
    if current == "":
        return target
    else:
        current_hex = binascii.hexlify(current.encode('utf-8', 'replace'))
        current_hex = int(current_hex, 16)
        target_hex = binascii.hexlify(target.encode('utf-8', 'replace'))
        target_hex = int(target_hex, 16)
        if target_hex < current_hex:
            return target
        else:
            return current


minimum_char = 'z'
for item in s:
    minimum_char = get_smaller(item, minimum_char)

flg = False
for _ in range(k):
    tmp_candidates = []
    for _ in range(len(candidates)):
        cand = candidates.pop(0)
        ret = get_smaller(cand, ret)
        candr = cand[::-1]
        new_s = cand + candr

        cnt = 0
        for i in range(1, len(new_s) - n + 1):
            new_cand = new_s[i:i+n]
            if new_cand in visited:
                cnt += 1
            else:
                visited.add(new_cand)
                tmp_candidates.append(new_cand)
                ret = get_smaller(new_cand, ret)
        if cnt == len(new_s) - n or ret == minimum_char * n:
            flg = True
        if flg:
            break
    if flg:
        break
    else:
        renewal_candidates = []
        max_len = 0
        for item in tmp_candidates:
            tmp_len = 0
            for i in range(n-1, -1, -1):
                if item[i] == minimum_char:
                    tmp_len += 1
                else:
                    break
            if tmp_len > max_len:
                max_len = tmp_len
                if len(renewal_candidates) != 0:
                    renewal_candidates = [item]
                else:
                    renewal_candidates.append(item)
            elif tmp_len == max_len:
                if len(renewal_candidates) == 0:
                    renewal_candidates = [item]
                else:
                    renewal_candidates.append(item)

        if len(renewal_candidates) != 0:
            candidates.extend(renewal_candidates)
        else:
            candidates.extend(tmp_candidates)

print(ret)

Submission status: Time Limit Exceeded

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

aaaa = False

# K >= 14ぐらいでSは辞書順最小の文字で埋め尽くされる。

# あまり意味はないが計算結果が大きすぎてバグっても嫌なので上限を作っておく
if K >= 15:
    aaaa = True
elif 2 ** K >= N:
    aaaa = True

# 最小の文字だけで埋め尽くされる場合
if aaaa:
    print(min(S)*N)
    exit()


def get_reverce_dict(s_str):
    U = s_str + s_str[::-1]
    minindex = 0
    for p in range(1, N + 1):
        if check_reverce_dict(U, minindex, p):
            minindex = p
    return U[minindex:minindex+N]


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


for _ in range(K - 1):
    S = get_reverce_dict(S)


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)
print(S)

Submission status: Time Limit Exceeded

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

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

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

print(s)

Submission status: Time Limit Exceeded

Solution code:
def E(S, N):
    T = S[::-1]
    U = S+T
    return sorted([U[i:N+i] for i in range(N)])[:N//2]

N, K = input().split()
N, K = int(N), int(K)
S = [input()]

for i in range(K):
    memory = []
    for s in S:
        memory.append(E(s, N))
    S = sorted([s for i in range(len(memory)) for s in memory[i]])[:N//2]
print(sorted(S)[0])

Submission status: Time Limit Exceeded

Solution code:
import binascii
n, k = [int(x) for x in input().split()]
s = input()

candidates = [s]
visited = set()
ret = ""


def get_smaller(target, current):
    if current == "":
        return target
    else:
        current_hex = binascii.hexlify(current.encode('utf-8', 'replace'))
        current_hex = int(current_hex, 16)
        target_hex = binascii.hexlify(target.encode('utf-8', 'replace'))
        target_hex = int(target_hex, 16)
        if target_hex < current_hex:
            return target
        else:
            return current


minimum_char = 'z'
for item in s:
    minimum_char = get_smaller(item, minimum_char)

flg = False
for _ in range(k):
    tmp_candidates = []
    for _ in range(len(candidates)):
        cand = candidates.pop(0)
        ret = get_smaller(cand, ret)
        candr = cand[::-1]
        new_s = cand + candr

        cnt = 0
        for i in range(1, len(new_s) - n + 1):
            new_cand = new_s[i:i+n]
            if new_cand in visited:
                cnt += 1
            else:
                visited.add(new_cand)
                tmp_candidates.append(new_cand)
                ret = get_smaller(new_cand, ret)
        if cnt == len(new_s) - n or ret == minimum_char * n:
            flg = True
        if flg:
            break
    if flg:
        break
    else:
        candidates.extend(tmp_candidates)

print(ret)

Submission status: Time Limit Exceeded

Solution code:
str = input()
a = str.split(" ")
n = (int)(a[0])
k = (int)(a[1])
str = input();
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]

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)

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:

"""

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]
    #print (u)
    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]
    #print (u)
    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)

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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]))

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution 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)))

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

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

aaaa = False

# K >= 14ぐらいでSは辞書順最小の文字で埋め尽くされる。

# あまり意味はないが計算結果が大きすぎてバグっても嫌なので上限を作っておく
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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]
  #print(ss)
  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
    #print(tmp[::-1])
    #print(ss)
    rev = []
  for x in range(lens+1):
    r = ss[x:lens+x]
    rev.append(r)
  sortrev = sorted(rev)
  print(sortrev[0])

Submission status: Runtime Error

Solution code:
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, 100))
print((mido[0] * ans + mido[ind:ind + n - ans])[:n])

Submission status: Runtime Error

Solution code:
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 ** (k - 1))
print((mido[0] * ans + mido[ind:ind + n - ans])[:n])

Submission status: Runtime Error

Solution code:
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 * m)
        exit(0)
    for c, i in l:
        if i <= n and c == a:
            s = min(s, u[i:i + n])
    if (k - p) % 2 == 0:
        s = s[::-1]
print(s)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
s = input()
m = min(s)
if k >= 20:
    print(m * n)
else:
    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
        a, j = max(l)
        for c, i in l:
            if i <= n and c == a:
                s = min(s, u[i:i + n])
        if (k - p) % 2 == 0:
            s = s[::-1]
    print(s)

Submission status: Runtime Error

Solution code:
from math import floor, log2
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(log2(N/n))):
    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])

Submission status: Runtime Error

Solution code:
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=list(ls[0])
if 2**k<n:
  y=n-2**k
  print(x[0]*(2**k)+x[1:y+1])
else:
  print(x[0]*n)

Submission status: Runtime Error

Solution 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)))

elif K>=13:
    print(MIN*N)

else:
    CAN=next(S)

    ANS=[]

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

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

        ANS.append(minimum(c))

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

Submission status: Runtime Error

Solution 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,MAX

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

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

else:
    CAN,MAX=next(S)

    ANS=[]

    for c in CAN:
        for j in range(K-2):
            c=next2(c,MAX)

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

        ANS.append(minimum(c))

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

Submission status: Runtime Error

Solution 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,MAX

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

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

else:
    CAN,MAX=next(S)

    ANS=[]

    for c in CAN:
        for j in range(K-2):
            c=next2(c,MAX)

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

        ANS.append(minimum(c))

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

Submission status: Runtime Error

Solution code:
import sys
n,k = map(int,input().split( ))
s = input()
r0 = list(reversed(s))
r = ''.join(r0)
s = s + r
l = len(s)
S = [s[i] for i in range(l)]

literal=list(set(S))
literal.sort()

small = literal[0]

i=0
mx=0
cnt = 0
now=-1
cnd=[]
while i<l:
    if s[i] == small:
        now = i
        cnt = 1
        i += 1
        try:
            while s[i] == small:
                cnt += 1
                i += 1
            if mx < cnt:
                cnd = []
                cnd.append(now)
                now == i
                mx = cnt
            elif mx == cnt:
                cnd.append(now)
                now = i
            else:
                now = i
        except:
            pass
    i += 1
if mx*2**k>=n:
    print(small*2**k)
    sys.exit
else:
    pass
cnd_string = []
addi = n - 2**k


for i in cnd:
    cnd_string.append(s[i + mx : i + mx + addi])
cnd_string.sort()
for t in cnd_string:
    if len(t) < addi:
        cnd_string.remove(t)
print(small*2**k + cnd_string[0])

Submission status: Runtime Error

Solution code:
import sys
n,k = map(int,input().split( ))
s = input()
r0 = list(reversed(s))
r = ''.join(r0)
s = s + r
l = len(s)
S = [s[i] for i in range(l)]

literal=list(set(S))
literal.sort()

small = literal[0]

i=0
mx=0
cnt = 0
now=-1
cnd=[]
while i<l:
    if s[i] == small:
        now = i
        cnt = 1
        i += 1
        try:
            while s[i] == small:
                cnt += 1
                i += 1
                if mx < cnt:
                    cnd = []
                    cnd.append(now)
                    now == i
                    mx = cnt
                elif mx == cnt:
                    cnd.append(now)
                    now = i
                else:
                    now = i
        except:
            pass
    i += 1
if mx*2**k>=n:
    print(small*2**k)
    sys.exit
else:
    pass
cnd_string = []
addi = n - 2**k


for i in cnd:
    cnd_string.append(s[i + mx : i + mx + addi])
cnd_string.sort()
for t in cnd_string:
    if len(t) < addi:
        cnd_string.remove(t)
print(small*2**k + cnd_string[0])