CF196D.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.

在字符串相关的问题中，我们常常需要找到一个具有特定性质的字符串。本题的出题人不愿花费时间构思某个字符串的名称，因此将其称为“好字符串”。一个字符串被称为好字符串，当且仅当它不包含长度大于等于 $ d $ 的回文子串。

给定一个仅由小写英文字母组成的字符串 $ s $。请找出一个长度为 $ |s| $、也仅由小写英文字母组成的好字符串 $ t $，使得 $ t $ 在字典序上严格大于 $ s $；在所有满足条件的字符串中，$ t $ 应为字典序最小者。

我们称非空字符串 $ s[a \dots b] = s_a s_{a+1} \dots s_b $（其中 $ 1 \le a \le b \le |s| $）为字符串 $ s = s_1 s_2 \dots s_{|s|} $ 的一个子串。

一个非空字符串 $ s = s_1 s_2 \dots s_n $ 被称为回文串，当且仅当对所有从 $ 1 $ 到 $ n $ 的 $ i $，均满足 $ s_i = s_{n-i+1} $。换言之，回文串正读与反读完全相同。

字符串 $ x = x_1 x_2 \dots x_{|x|} $ 在字典序上大于字符串 $ y = y_1 y_2 \dots y_{|y|} $，当且仅当以下任一条件成立：

• $ |x| > |y| $，且 $ x_1 = y_1,, x_2 = y_2,, \dots,, x_{|y|} = y_{|y|} $；
• 或存在某个数 $ r $（满足 $ r < |x| $ 且 $ r < |y| $），使得 $ x_1 = y_1,, x_2 = y_2,, \dots,, x_r = y_r $，但 $ x_{r+1} > y_{r+1} $。
  此类字符串中的字符按其 ASCII 码值进行比较。

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·105 characters. The string consists of lowercase English letters.

第一行包含一个整数 $d$（$1 \leq d \leq |s|$）。

第二行包含一个非空字符串 $s$，其长度不超过 $4 \cdot 10^5$ 个字符。该字符串仅由小写英文字母组成。

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).

输出字典序紧接在字符串 s 之后的“好字符串”，该字符串需与 s 长度相同，且仅由小写英文字母组成。如果不存在这样的字符串，则输出 "Impossible"（不带引号）。