- Time limit: 1.00 s
- Memory limit: 512 MB
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