C - Best Password

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]

ただし A2 以上 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.


Source Name

KUPC2017