Problem C: Phone Number

Problem

株式会社ウクニキアの電話番、デンさんは毎日とても長い電話番号を電話に入力しています。
ある日余りにも疲れたデンさんは、疲れからか驚くべき考えに至りました。
「電話のボタンの配置を並べ替えたら少しでも楽できるのでは？！」

電話には$3 \times 3$で等間隔に区切られた正方形があり、9個のマスには並べ替えることのできる1から9までのボタンがそれぞれ1つずつついています。
電話番号を打つ際、デンさんは片手だけを使って、次の二つの操作を行うことができます。

• 人差し指を今触れているボタンに辺で隣接するいずれかのボタンに触れるように移動させる。
• 人差し指が触れているボタンを押す。

最初、人差し指は1から9までのいずれかのボタンに触れるように置くことができます。
デンさんは、最初のボタンを押してから最後のボタンを押し終わるまでの、人差し指の移動回数を最も小さくできる配置を効率的と考えています。

さて、ここに長さ$N$のお得意先の電話番号があります。
お得意先の電話番号だけ考えた時に、どのような配置が一番効率的でしょうか？
ボタンを並び替えることで、その配置を作ってください。

Input

入力は以下の形式で与えられる。

$N$
$S$

1行目にお得意先の電話番号の長さ$N$が与えられる。
2行目にお得意先の電話番号が1行に与えられる。

Constraints

入力は以下の条件を満たす。

• $1 \leq N \leq 10^5 $
• $S$は1から9までのいずれかの数字からなる文字列

Output

最も効率的な配置を、3行に空白を入れずに出力せよ。
但し、解答となり得る配置が複数ある場合は、左上の枠から
123
456
789
の順序で数字を並べた際に辞書順で最小となるようなものを出力せよ。

Sample Input 1

10
1236547896

Sample Output 1

123
456
789

Sample Input 2

11
31415926535

Sample Output 2

137
456
892

Note

Link

 

---