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] = sasa + 1... sb (1 ≤ a ≤ b ≤ |s|) a substring of string s = s1s2... s|s|.

A non-empty string s = s1s2... sn is called a palindrome if for all i from 1 to n the following fulfills: si = sn - i + 1. In other words, palindrome read the same in both directions.

String x = x1x2... x|x| is lexicographically larger than string y = y1y2... y|y|, if either |x| > |y| and x1 = y1, x2 = y2, ... , x|y| = y|y|, or there exists such number r (r < |x|, r < |y|), that x1 = y1, x2 = y2, ... , xr = yr and xr + 1 > yr + 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·105 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).

Examples

Input

3
aaaaaaa


Output

aabbcaa


Input

3
zzyzzzz


Output

Impossible


Input

4
abbabbbabbb


Output

abbbcaaabab
#include <bits/stdc++.h>
using namespace std;
inline int read() {
  int num = 0;
  char c = getchar();
  if (c == '-') return -read();
  while (c >= '0' && c <= '9') {
    num = (num << 3) + (num << 1) + c - '0';
    c = getchar();
  }
  return num;
}
inline long long READ() {
  long long num = 0;
  char c = getchar();
  if (c == '-') return -READ();
  while (c >= '0' && c <= '9') {
    num = (num << 3) + (num << 1) + c - '0';
    c = getchar();
  }
  return num;
}
int d;
string s;
long long h1[500007], h2[500007], r1[500007], r2[500007];
const int Ha1 = 29, Ha2 = 20007;
const int Mod1 = 1000000007, Mod2 = 1000000009;
long long mii1[500007], mii2[500007], fmii1[500007], fmii2[500007];
int start;
bool add1(int pos) {
  while (pos >= 0 && s[pos] == 'z') {
    s[pos] = 'a';
    pos--;
  }
  if (pos < 0) return 0;
  s[pos]++;
  start = pos;
  return 1;
}
long long getha(long long ha[], long long mii[], int pos, int len,
                long long m0d) {
  long long HA = ha[pos];
  if (pos - len >= 0) HA -= ha[pos - len] * mii[len] % m0d;
  HA %= m0d;
  if (HA < 0) HA += m0d;
  return HA;
}
inline long long ksmii(int a, int b, int m0d) {
  if (!b) return 1;
  long long ans = ksmii(a, b / 2, m0d);
  ans = ans * ans % m0d;
  if (b % 2) ans = ans * a % m0d;
  return ans;
}
long long gethar(long long ha[], long long mii[], long long fmii[], int pos,
                 int len, long long m0d) {
  long long HA = ha[pos];
  if (pos - len >= 0) HA -= ha[pos - len];
  HA %= m0d;
  if (HA < 0) HA += m0d;
  HA *= fmii[pos - len + 1];
  HA %= m0d;
  return HA;
}
pair<long long, long long> hashit(int pos, int len) {
  return make_pair(getha(h1, mii1, pos, len, Mod1),
                   getha(h2, mii2, pos, len, Mod2));
}
pair<long long, long long> hashitr(int pos, int len) {
  return make_pair(gethar(r1, mii1, fmii1, pos, len, Mod1),
                   gethar(r2, mii2, fmii2, pos, len, Mod2));
}
bool haa(int p1, int p2, int len) {
  return hashitr(p1, len) != hashit(p2, len);
}
bool isnthw(int pos, int len) {
  if (len % 2)
    return haa(pos, pos - len / 2 - 1, len / 2);
  else
    return haa(pos, pos - len / 2, len / 2);
}
bool isnthw(int pos) {
  if (pos + 1 >= d && !isnthw(pos, d)) return 0;
  if (pos + 1 >= d + 1 && !isnthw(pos, d + 1)) return 0;
  return 1;
}
int main() {
  cin >> d >> s;
  mii1[0] = 1;
  for (int i = 1; i < 500007; i++) {
    mii1[i] = mii1[i - 1] * Ha1 % Mod1;
    fmii1[i] = ksmii(mii1[i], Mod1 - 2, Mod1);
  }
  mii2[0] = 1;
  for (int i = 1; i < 500007; i++) {
    mii2[i] = mii2[i - 1] * Ha2 % Mod2;
    fmii2[i] = ksmii(mii2[i], Mod2 - 2, Mod2);
  }
  if (d == 1 || !add1(((int)(s).size()) - 1)) return printf("Impossible\n"), 0;
  int gfj = ((int)(s).size());
  for (int i = 0; i < ((int)(s).size()); i++) {
    if (i >= gfj) s[i] = 'a';
    h1[i] = ((i ? h1[i - 1] : 0) * Ha1 + s[i] - 'a' + 1) % Mod1;
    h2[i] = ((i ? h2[i - 1] : 0) * Ha2 + s[i] - 'a' + 1) % Mod2;
    r1[i] = ((i ? r1[i - 1] : 0) + (s[i] - 'a' + 1) * mii1[i]) % Mod1;
    r2[i] = ((i ? r2[i - 1] : 0) + (s[i] - 'a' + 1) * mii2[i]) % Mod2;
    if (!isnthw(i)) {
      if (!add1(i)) return printf("Impossible\n"), 0;
      gfj = start + 1;
      i = start - 1;
    }
  }
  cout << s << endl;
  return 0;
}
