And where the are the phone numbers?

You are given a string s consisting of lowercase English letters and an integer k. Find the lexicographically smallest string t of length k, such that its set of letters is a subset of the set of letters of s and s is lexicographically smaller than t.

It's guaranteed that the answer exists.

Note that the set of letters is a set, not a multiset. For example, the set of letters of abadaba is {a, b, d}.

String p is lexicographically smaller than string q, if p is a prefix of q, is not equal to q or there exists i, such that pi < qi and for all j < i it is satisfied that pj = qj. For example, abc is lexicographically smaller than abcd , abd is lexicographically smaller than abec, afa is not lexicographically smaller than ab and a is not lexicographically smaller than a.

Input

The first line of input contains two space separated integers n and k (1 ≤ n, k ≤ 100 000) — the length of s and the required length of t.

The second line of input contains the string s consisting of n lowercase English letters.

Output

Output the string t conforming to the requirements above.

It's guaranteed that the answer exists.

Examples

Input

3 3
abc


Output

aca


Input

3 2
abc


Output

ac


Input

3 3
ayy


Output

yaa


Input

2 3
ba


Output

baa

Note

In the first example the list of strings t of length 3, such that the set of letters of t is a subset of letters of s is as follows: aaa, aab, aac, aba, abb, abc, aca, acb, .... Among them, those are lexicographically greater than abc: aca, acb, .... Out of those the lexicographically smallest is aca.
import sys 
import math
from collections import Counter
from operator import itemgetter
import queue

def IO():
	sys.stdin=open("pyinput.txt", 'r')
	sys.stdout=open("pyoutput.txt", 'w')

def GCD(a, b):
	if(b==0): return a
	else: return GCD(b, a%b)

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

def scan(TYPE_1, TYPE_2=0):
	if(TYPE_1==int):
		return map(int, sys.stdin.readline().strip().split())
	elif(TYPE_1==float):
		return map(float, sys.stdin.readline().strip().split())
	elif(TYPE_1==list and TYPE_2==float):
		return list(map(float, sys.stdin.readline().strip().split()))
	elif(TYPE_1==list and TYPE_2==int):
		return list(map(int, sys.stdin.readline().strip().split()))
	elif(TYPE_1==str):
		return sys.stdin.readline().strip()
	else: print("ERROR!!!!") 



def main():
	
	n, k=scan(int)
	s=scan(str)
	st=sorted(list(set(s)))

	ans=list(s[:min(k, n)])

	if(k>n):
		print(''.join(ans), end='')
		for i in range(len(ans), k):
			print(st[0], end='')
		print()
		return

	for i in range(-1, -k-1, -1):
		ch=ord(ans[i])+1

		for ch in range(ch, 123):
			if(chr(ch) in st):
				ans[i]=chr(ch)
				print(''.join(ans))
				return
		ans[i]=st[0]




# IO()
main()