在字符串问题中,人们通常必须找到具有某些特定属性的字符串。问题作者不愿意浪费时间为某些字符串考虑名称,因此他们认为它很好。如果一个字符串没有长于或等于 d 的回文子串,则该字符串是好的。
给定字符串 s,仅由小写英文字母组成。找到一个好的字符串t,长度|s|,由小写英文字母组成,按字典顺序比s大。在所有此类字符串中,字符串 t 必须按字典顺序最小。
我们将非空字符串 s[a ... b] = sasa + 1... sb (1 ≤ a ≤ b ≤ |s|) 称为字符串 s = s1s2... s|s| 的子串。
如果对于从 1 到 n 的所有 i 满足以下条件,则非空字符串 s = s1s2... sn 称为回文:si = sn - i + 1。换句话说,回文在两个方向上读取相同。
字符串 x = x1x2... x|x|按字典顺序大于字符串 y = y1y2... y|y|,如果 |x| > |y|且 x1 = y1, x2 = y2, ... , x|y| = y|y|,或者存在这样的数字 r (r < |x|, r < |y|),即 x1 = y1, x2 = y2, ... , xr = yr 和 xr + 1 > yr + 1。此类字符串中的字符像它们的 ASCII 代码一样进行比较。
输入
第一行包含整数 d (1 ≤ d ≤ |s|)。
第二行包含一个非空字符串s,其长度不超过4·105个字符。该字符串由小写英文字母组成。
输出
打印按字典顺序位于 s 之后、长度相同且仅由小写英文字母组成的良好字符串。如果这样的字符串不存在,则打印“Impossible”(不带引号)。
示例
输入 #1
3 aaaaaaa
输出 #1
aabbcaa
输入 #2
3 zzyzzzz
输出 #2
Impossible
输入 #3
4 abbabbbabbb
输出 #3
abbbcaaabab