ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs
Login Register

5033: Cutting the Line

内存限制：256 MB 时间限制：2 S
题面：传统 评测方式：文本比较 上传者：
提交：1 通过：1
提交提交记录统计Web Board

题目描述

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

输入样例 复制

输出样例 复制

分类标签