Uolevi has invented a new way of encrypting messages. Uolevis encryption processes each character of the message and changes character x into f(x). To be sure of security, Uolevi applies the encryption k times to the message. Your task is to decrypt the encrypted message, given f and k.

Input

The first line of input contains string f and integer k. Length of string f is 26 characters. If the ith character of f is c_i, the encryption turns the ith character of alphabet into c_i. The second line contains one string S, the encrypted message. All characters of the input are lowercase english letters from a to z.

Output

Output the original message. If the message can't be decrypted uniquely or there are no valid answers, output impossible

Constraints

• 1 \le k \le 10^9
• 1 \le |S| \le 100

Examples

Input:

bcdefghijklmnopqrstuvwxyza 1
bzcbcuv

Output:

aybabtu

Input:

nopqrstuvwxyzabcdefghijklm 2
goodidea

Output:

goodidea

Input:

aaaaaaaaaaaaaaaaaaaaaaaaaa 3
aaaa

Output:

impossible

Input:

aaaaaaaaaaaaaaaaaaaaaaaaaa 3
lol

Output:

impossible