跳到主要内容
图灵 OJTURING / ONLINE JUDGE

#F1502. Cutting the Line

  • ID: 1508
  • 传统题
  • 2000ms
  • 256MiB
  • 尝试: 0
  • AC · 已通过: 0
  • 教学难度:挑战
  • 上传者:
  • 后缀结构
  • 字符串
  • 挑战
  • 难度
  • 共享题库
  • Codeforces
  • 英文题面
  • 题目来源
  • 题面语言

Cutting the Line

题目描述

E. Cutting the Line
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a non-empty line s and an integer k. The following operation is performed with this line exactly once:

  • A line is split into at most k non-empty substrings, i.e. string s is represented as a concatenation of a set of strings s=t1+t2+...+tm, 1≤m≤k.
  • Some of strings ti are replaced by strings tir, that is, their record from right to left.
  • The lines are concatenated back in the same order, we get string s'=t'1t'2... t'm, where t'i equals ti or tir.

Your task is to determine the lexicographically smallest string that could be the result of applying the given operation to the string s.

Input

The first line of the input contains string s (1≤|s|≤5000000), consisting of lowercase English letters. The second line contains integer k (1≤k≤|s|)− the maximum number of parts in the partition.

Output

In the single line print the lexicographically minimum string s' which can be obtained as a result of performing the described operation.

Examples
Input
aba
2
Output
aab
Input
aaaabacaba
2
Output
aaaaabacab
Input
bababa
1
Output
ababab
Input
abacabadabacaba
4
Output
aababacabacabad

题目来源:fps-www.educg.net-codeforce-1-2833.xml.zip;FPS 共享题包,题包内第 1013 题。保留原作者与原赛事署名。