問題文

初雪くんは、桜さんから NN 桁の整数 DD を貰いました。
初雪くんは大きい整数が好きなので、次の操作を任意の回数行うことによって DD を最大化することにしました。

操作 : DD を巡回シフトする。つまり、 DDd1d2d3dN1dNd_1d_2d_3 \ldots d_{N-1}d_N だったとすると、 DDdNd1d2dN2dN1d_Nd_1d_2 \ldots d_{N-2}d_{N-1} で置き換える。

DD を最大化したときの値を求めてください。

  

制約

  • 1N5000001\leq N \leq 500000
  • DD はleading-zeroを含まない
  • 入力は全て整数

  

入力

入力は以下の形式で標準入力から与えられます。

NN
DD

  

出力

答えを出力してください。

  

入力例1

6
178096

出力例1

961780

178096178096 に対して操作を 22 回施すと、 178096617809961780178096→617809→961780 と変化します。これ以上大きな整数を作ることは出来ないので、 961780961780 と出力すると正解となります。  
 

入力例2

1
0

出力例2

0

leading-zeroを含む入力はありませんが、 00 はvaildな入力です。  
 

入力例3

2
99

出力例3

99

何回操作を施しても値が変わらないかもしれません。
 

入力例4

88
9742359064609728426386349679303923450934099239720712419992864932859686221300012480903274

出力例4

9992864932859686221300012480903274974235906460972842638634967930392345093409923972071241

DD が64bit整数に収まらないこともあります。

Submit


Go (1.21)