← 返回题目列表

Codeforces · 196/D

D. 下一个好弦

中文机器翻译题面 查看原题

在字符串问题中,人们通常必须找到具有某些特定属性的字符串。问题作者不愿意浪费时间为某些字符串考虑名称,因此他们认为它很好。如果一个字符串没有长于或等于 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