Problem
プロシュートはペンダントを付けるのが大好きです。特に小文字のラテン文字で単語が刻まれたものが好きで、これしか身に着けていない。
Prosciutto は自分で新しいペンダントを買いたくて、専門店に行きました。
店で、彼は、回文の碑文が入ったペンダントが今特に流行していると言われた.もちろん、プロシュートは自分で1つ選ぶことにしましたが、彼は選択を決めることができませんでした.
それから彼は、現在のペンダントの碑文から単語を取り出し、同じ長さの心地よい単語を考え出し、それらを新しいペンダントの碑文の単語に変換する必要があるという古代の慣習を教えられました. br />
変換操作は次のとおりです。
1) 対応する位置の記号には、アルファベットでのこれらの記号の位置に対応する番号が割り当てられます。したがって、文字 d は数字の 4 に対応し、文字 a - 1 に対応します。
2) 対応する位置の数字が合計されます。金額がラテン アルファベットのサイズを超える場合は、そこから 26 が差し引かれます。
3) 新しい単語に受け取った金額に対応する文字が追加されます。
したがって、「アバ」という言葉は、と「バブ」は「ccc」に変換され、「zxc」は「zxc」に変換されます。と「bbb」 「bze」で。
プロシュートは現在、長さ n の碑文 s のペンダントを持っていますが、楽しい言葉は頭に浮かびません。しかし、彼は、辞書編集的に最小限の単語を使用して、現在のキャプションをトレンディな回文キャプションに変換することは興味深いと考えました.
Prosciutto の現在のペンダントには既に回文の碑文があるかもしれないという事実にもかかわらず、Prosciutto はまだ新しいものを選択したいと考えています.
プロシュートは今日はあまり眠れなかったので、現在の碑文をどの単語で変換する必要があるか判断できません。彼を助けてください。
入力:
最初の行には、自然数 n (1 ≤ n ≤ 10
5) が含まれています。これは、現在のプロシュート ペンダントの刻印の長さです。
2 行目には文字列 s が含まれています。これは碑文そのものです。
出力:
単一行を出力します。これは、既存のキャプションを回文キャプションに変換するために必要な長さの単語です。
例:
<本体>
| 入力 |
出力 |
2
広告 |
斧 |
7
アバカバ |
あああああ |
説明:
最初の例では、単語「ax」が- 辞書編集的に最小限で、既存の碑文「ad」を変換して、回文の碑文を取得できます（「bb」になります）。