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_as_a + 1... s_b (1 ≤ a ≤ b ≤ |s|) a substring of string s = s₁s₂... s_|s|.

A non-empty string s = s₁s₂... 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₁x₂... x_|x| is lexicographically larger than string y = y₁y₂... y_|y|, if either |x| > |y| and x₁ = y₁, x₂ = y₂, ... , x_|y| = y_|y|, or there exists such number r (r < |x|, r < |y|), that x₁ = y₁, x₂ = y₂, ... , x_r = y_r and x_r + 1 > y_r + 1. Characters in such strings are compared like their ASCII codes.

Input

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

Output

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

Idx	Name	Rating
A	Lexicographically Maximum Subsequence	1100
B	Infinite Maze	2000
C	Paint Tree	2200
D	The Next Good String	2800
E	Opening Portals	2600

Codeforces Round 124 (Div. 1)