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.
#coding=utf-8  
#给一个长度为n的字符串s，求字典序最小的字符串a，使a的长度为t，
#且a的字典序大于s，且a的字符集是s的子集
n, t = [int(i) for i in raw_input().split()]#接收第一行输入的数字
s = raw_input().strip()#接收第二行输入的字符串
chars = set(s)#为字符串中的每个元素创建集合
sort = sorted(chars)
if t > n:
	print s + (t - n) * min(chars)#返回列表元素中的最小值
else:
	o = s[:t]#取输入字符串中的前t个元素
	m = 0
	for i in range(len(o) - 1, -1, -1):#从 t-1 减到 0
		#range(0, -10, -1) -> [0, -1, -2, -3, -4, -5, -6, -7, -8, -9]
		f = sort.index(o[i])
		if f != len(sort) - 1:
			o = o[:i] + sort[f + 1] + o[i + 1:]	
			m = i
			break
	o = o[:m + 1] + min(sort) * (t - m - 1)
	print o