D. Следующая хорошая строка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

В задачах на строки часто требуется найти строку, обладающую какими-то особыми свойствами. В очередной раз авторам задачи было лень придумывать название для такой строки, поэтому они назвали ее хорошей. Строка называется хорошей, если в ней нет подстрок-палиндромов длины большей или равной d.

Дана строка s, состоящая только из строчных латинских букв. Найдите хорошую строку t длины |s|, состоящую из строчных латинских букв, и лексикографически большую, чем s. Из всех таких строк строка t должна быть лексикографически минимальной.

Непустую строку s[a ... b] = sasa + 1... sb (1 ≤ a ≤ b ≤ |s|) будем называть подстрокой строки s = s1s2... s|s|.

Непустая строка s = s1s2... sn называется палиндромом, если для всех i от 1 до n выполняется 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» (без кавычек).

Примеры
Входные данные
3
aaaaaaa
Выходные данные
aabbcaa
Входные данные
3
zzyzzzz
Выходные данные
Impossible
Входные данные
4
abbabbbabbb
Выходные данные
abbbcaaabab