/ 
Time Limit: 1 sec / Memory Limit: 256 MB
配点 : 100 点
問題文
京都大学のある建物にはパスワードを知っている者だけが認証を通り、入ることができます。
パスワードは英小文字からなる文字列であり、建物の利用者であるあなたにはこのパスワードが知らされています。
この認証システムは入力されたパスワードのハッシュ値を求め、そのハッシュ値を使って照合されるというシステムです。
長さ N の文字列 S のハッシュ値は、i 文字目を S_i として、以下の式で求められます。
A^1 \times C[S_1] + A^2 \times C[S_2] + ... + A^N \times C[S_N]
ただし A は 2 以上 10 以下の整数の定数であり、C[a]=1, C[b]=2, ..., C[z]=26 です。
あなたはとても忙しく、出来る限り短い入力で認証を済ませたいと考えています。
本来のパスワードと同じハッシュ値を持つような最短の文字列を求めてください。 条件を満たす最短の文字列が複数ある場合は、辞書順最大のものを求めてください。
制約
- 2 \leq A \leq 10
- A は整数である。
- 1 \leq |S| \leq 1,000
- S は英小文字からなる文字列である。
入力
入力は以下の形式で標準入力から与えられる。
A S
出力
求める文字列を 1 行に出力せよ。
入力例1
2 kupc
出力例1
yzp
元の文字列のハッシュ値は
2^1 \times 11 + 2^2 \times 21 + 2^3 \times 16 + 2^4 \times 3 = 282
です。出力文字列のハッシュ値も同じく
2^1 \times 25 + 2^2 \times 26 + 2^3 \times 16 = 282
です。
入力例2
10 abcde
出力例2
utuvc
入力例3
4 zzz
出力例3
zzz
入力例4
9 kyotouniversityprogrammingcontest
出力例4
txxsxtwztwyrrsyyzwxyrtuzuxsvvswzs
ハッシュ値は非常に大きくなることがあります。
Score : 100 points
Problem Statement
One of the buildings in Kyoto University requires a password to enter.
This password consists of lowercase alphabets and you, one of those who use the building, know the password.
The authentication system of the building calculates a hash value from the password that is entered, and checks whether the hash value matches.
The hash value of string S of length N is calculated based on the following formula.
A^1 \times C[S_1] + A^2 \times C[S_2] + ... + A^N \times C[S_N]
A is an integer more than or equal to 2 and less than or equal to 10, and C[a]=1, C[b]=2, ..., C[z]=26.
You are so busy that you want to pass the authentication with as short password as possible.
Find the shortest password, the hash value of which is the same as that of the original password. If multiple passwords of the minimum length exist, find the lexicographically maximum one.
Constraints
- 2 \leq A \leq 10
- A is an integer.
- 1 \leq |S| \leq 1,000
- S consists of lowercase alphabets.
Input
Input is given from Standard Input in the following format:
A S
Output
Print the password required above.
Sample Input 1
2 kupc
Sample Output 1
yzp
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 is also
2^1 \times 25 + 2^2 \times 26 + 2^3 \times 16 = 282.
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
The hash value is very large in some cases.