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
import java.io.* ;
import java.util.*;

import static java.lang.Math.* ;
import static java.util.Arrays.* ;

public class A {
	
	public static void main(String[] args) throws IOException {
		
		new A().solveProblem();
		
		out.close();
	}

	static Scanner in = new Scanner(new InputStreamReader(System.in));
	static BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
	static PrintStream out = new PrintStream(new BufferedOutputStream(System.out));
	
	
	static final long MOD = 1000000007 ;
	static final long d = 26 ;
	
	int k ;
	char[] cs ;
	int n ;
	static long[] macht ;
	public void solveProblem() throws IOException {		
	
		k = Int() ;
		cs = Line().toCharArray() ;
		n = cs.length ;
		
		macht = new long[n] ;
		macht[0] = 1 ;
		for( int i = 1 ; i < n ; i++ )
			macht[i] = (macht[i-1]*d) % MOD ;
		
		voor = new Fenwick(n) ;
		achter = new Fenwick(n) ;

		for( int i = 0 ; i < n ; i++ ){
			
			int v = cs[i] - 'a' ;
			voor.adjust(1+i, (v*macht[i])%MOD ) ;
			
			v = cs[n-i-1] - 'a' ;
			achter.adjust(n-i, (v*macht[i])%MOD ) ;
		}
		
		int z = n - 1 ;
		for( int i = k -1 ; i < n ; i++ ){

			if( pa(i)){
				z = i ;
				break ;
			}
		}

		boolean ok = false ;
		
		while( ! ok ){
			
			while( cs[z] == 'z'){
				voor.adjust(z+1, (macht[z]*-25) % MOD ) ;
				achter.adjust(z+1, (macht[n-z-1]*-25) % MOD ) ;
				cs[z--] = 'a' ;
				if( z < 0 ){
					out.println("Impossible") ;
					return ;
				}
			}
			
		
			cs[z]++ ;
			voor.adjust(z+1, (macht[z]) % MOD ) ;
			achter.adjust(z+1, (macht[n-z-1]) % MOD ) ;
			ok = !pa(z) ;
		}
		
		for( int i = z + 1 ; i < n ; i++ ){
			
			for( char c = 'a' ; c <= 'c' ; c++){
				voor.adjust(i+1, (macht[i]*(-cs[i]+c)) % MOD ) ;
				achter.adjust(i+1, (macht[n-i-1]*(-cs[i]+c)) % MOD ) ;
				cs[i] = c ;
				
				if( !pa(i))
					break ;
			}
		}
		
	

		out.println(new String(cs)) ;
		
		
		
	}

	static boolean deb = false ;
	boolean pa(int i){
		return (i - k + 1 >= 0 && palin(i-k+1,i)) || ( i - k >= 0 && palin(i-k,i)) ;
	}
	private boolean palin(int van, int tot) {
		
		int l = tot - van + 1 ;

		if( deb )
			p(voor.rsq(van+1,van+l/2) , achter.rsq(van+l/2+1,tot+1) ) ;
		if( l % 2 == 0 )
			return (voor.rsq(van+1,van+l/2) * macht[n-1-van] ) % MOD == (achter.rsq(van+l/2+1,tot+1) * macht[tot] ) % MOD ;
		else
			return ( voor.rsq(van+1,van+l/2) * macht[n-1-van] ) % MOD == (achter.rsq(van+l/2+2,tot+1)* macht[tot] ) % MOD ;
		
	}

	Fenwick voor ;
	Fenwick achter ;
	
	class Fenwick{
		
		public Fenwick( int n ){
			fenwick = new long[n+1] ;
			this.n = n ;
		}
		int n ; 
		long[] fenwick ; // aanmaken met n + 1 !!!!!!
		
		long rsq( int k ){
			long som = 0 ;
			
			while( k > 0 ){
				som = (som+fenwick[k])%A.MOD ;
				k -= (k & (-k)) ;
			}
			
			return som ;
			
		}
		
		long rsq( int l, int h){
			if( l > h )
				return 0 ;
			if( l == 0 )
				return rsq( h ) ;
			return (MOD+(rsq( h ) - rsq( l-1 )) % MOD) % MOD ;
		}
		
		void adjust( int k, long v){
			while( k < fenwick.length ){
				fenwick[k] += v ;
				k += (k & (-k)) ;
			}
		}

	}
	
	
	
	static String Line() throws IOException{
		return buf.readLine() ;
	}

	static int bufI = 0 ;
	static int[] bufInts = new int[0] ;
	
	static int Int() throws IOException{
		if( bufI == bufInts.length )
			bufReaderNInts() ;
		return bufInts[bufI++] ;
	}
	
	static int[] Int( int n ) throws IOException{
		int[] res = new int[n] ;
		for( int i = 0 ; i < n ; i++ )
			res[i] = Int() ;
		return res ;
	}
	
	static void bufReaderNInts() throws IOException{		
		String[] ss = buf.readLine().split(" ") ;
		bufInts = new int[ss.length] ;
		for( int i = 0 ; i < ss.length ; i++ ){
			bufInts[i] = Integer.parseInt(ss[i]) ;
		}
		bufI = 0 ;
	}
	
	static int bufL = 0 ;
	static long[] bufLongs = new long[0] ;
	
	static long Long() throws IOException{
		if( bufL == bufLongs.length )
			bufReaderNLongs() ;
		return bufLongs[bufL++] ;
	}
	
	static long[] Long( int n ) throws IOException{
		long[] res = new long[n] ;
		for( int i = 0 ; i < n ; i++ )
			res[i] = Long() ;
		return res ;
	}
	
	static void bufReaderNLongs() throws IOException{		
		String[] ss = buf.readLine().split(" ") ;
		bufLongs = new long[ss.length] ;
		for( int i = 0 ; i < ss.length ; i++ ){
			bufLongs[i] = Long.parseLong(ss[i]) ;
		}
		bufL = 0 ;
	}
	
	static int[] toArray( ArrayList<Integer> lijst ){
		int[] res = new int[lijst.size()] ;
		int t = 0 ;
		for( int i : lijst)
			res[t++] = i;
		return res ;
	}
	
	static void p( Object ...p){
		System.out.println(Arrays.deepToString(p));
	}
	
	static void wr( int[] rij ){
		for( int i = 0 ; i < rij.length - 1 ; i++ ) 
			out.print(rij[i] + " ") ;
		out.println(rij[rij.length-1]);
		
	}

	static void wr( long[] rij ){
		for( int i = 0 ; i < rij.length - 1 ; i++ ) 
			out.print(rij[i] + " ") ;
		out.println(rij[rij.length-1]);
		
	}
	
	
}