A8643 | The Next Good String

In problems on strings one often has to find a string with some particular properties. The problem authors were reluctant to waste time on thinking of a name for some string so they called it good. A string is good if it doesn't have palindrome substrings longer than or equal to $d$ .

You are given string $s$ , consisting only of lowercase English letters. Find a good string $t$ with length $|s|$ , consisting of lowercase English letters, which is lexicographically larger than $s$ . Of all such strings string $t$ must be lexicographically minimum.

We will call a non-empty string $s[a ... b]=s_{a}s_{a+1}...\ s_{b}$ $(1<=a<=b<=|s|)$ a substring of string $s=s_{1}s_{2}...\ s_{|s|}$ .

A non-empty string $s=s_{1}s_{2}...\ s_{n}$ is called a palindrome if for all $i$ from $1$ to $n$ the following fulfills: $s_{i}=s_{n-i+1}$ . In other words, palindrome read the same in both directions.

String $x=x_{1}x_{2}...\ x_{|x|}$ is lexicographically larger than string $y=y_{1}y_{2}...\ y_{|y|}$ , if either $|x|>|y|$ and $x_{1}=y_{1},x_{2}=y_{2},...\ ,x_{|y|}=y_{|y|}$ , or there exists such number $r$ $(r<|x|,r<|y|)$ , that $x_{1}=y_{1},x_{2}=y_{2},...\ ,x_{r}=y_{r}$ and $x_{r+1}>y_{r+1}$ . Characters in such strings are compared like their ASCII codes.

The first line contains integer $d$ ( $1<=d<=|s|$ ).

The second line contains a non-empty string $s$ , its length is no more than $4·10^{5}$ characters. The string consists of lowercase English letters.

Print the good string that lexicographically follows $s$ , has the same length and consists of only lowercase English letters. If such string does not exist, print "Impossible" (without the quotes).