Problem Description

A certain building at Kyoto University can only be accessed by those who know the password.

The password is a string consisting of lowercase English letters, and you, as a user of the building, have been informed of this password.

This authentication system calculates the hash value of the input password and verifies it using the hash value.

The hash value of a string $ S $ of length $ N $ is calculated as follows, where $ S_i $ is the $ i $-th character:

$A^1\ \times\ C[S_1]\ +\ A^2\ \times\ C[S_2]\ +\ ...\ +\ A^N\ \times\ C[S_N]$

Here, $ A $ is a constant integer between $ 2 $ and $ 10 $, and $ C[a]=1 $, $ C[b]=2 $, $ ... $, $ C[z]=26 $.

You are very busy and want to complete the authentication with the shortest possible input.

Find the shortest string that has the same hash value as the original password. If there are multiple shortest strings that satisfy the condition, find the one that is lexicographically largest.

Input Format

The input is given from the standard input in the following format:

$ A $ $ S $

Output Format

Output the desired string in one line.

Sample Input and Output

Sample Input #1

2
kupc

Sample Output #1

yzp

Sample Input #2

10
abcde

Sample Output #2

utuvc

Sample Input #3

4
zzz

Sample Output #3

zzz

Sample Input #4

9
kyotouniversityprogrammingcontest

Sample Output #4

txxsxtwztwyrrsyyzwxyrtuzuxsvvswzs

Notes/Hints

Constraints

• $2\ \leq\ A\ \leq\ 10$
• $ A $ is an integer.
• $1\ \leq\ |S|\ \leq\ 1,000$
• $ S $ is a string consisting of lowercase English letters.

Sample Explanation 1

The hash value of the original string is $2^1\ \times\ 11\ +\ 2^2\ \times\ 21\ +\ 2^3\ \times\ 16\ +\ 2^4\ \times\ 3\ =\ 282$. The hash value of the output string is also $2^1\ \times\ 25\ +\ 2^2\ \times\ 26\ +\ 2^3\ \times\ 16\ =\ 282$.

Sample Explanation 4

The hash value can be very large.

见题面 Input 部分

见题面 Output 部分