問題文

この問題においては、「$1$ 番目の文字」で文字 a を、「$2$ 番目の文字」で文字 b を、...、「$26$ 番目の文字」で文字 z を指すものとします。

英小文字からなる文字列 $S$ が与えられます。

あなたは $1\leq L\leq R\leq |S|$ となる整数 $L, R$ および $(1,2,\ldots,26)$ の順列 $(p_1,p_2,\ldots,p_{26})$ を選びます。その後、以下の手順で新たな文字列 $T$ を作ります。

1. $S'$ を $S$ の $L$ 文字目から $R$ 文字目を取り出してできる文字列とする。
2. $1$ 以上 $26$ 以下の全ての整数 $i$ について、$S'$ に含まれる「$i$ 番目の文字」を「$p_i$ 番目の文字」で置き換える。この操作は全ての $i$ に対して同時に行う。この結果できる文字列を $T$ とする。

$T$ として考えられる文字列のうち辞書順で最大のものを求めてください。

制約

• $1\leq |S|\leq 10^5$
• $S$ は英小文字のみからなる

入力例 1Copy

abcba

出力例 1Copy

zyzx

$L=2,R=5,(p_1,p_2,\ldots,p_{26})=(24,26,25,1,2,3,\ldots,23)$ とすると、$T$ は zyzx になります。$T$ としてありえるものの中でこれが辞書順で最大です。

入力例 2Copy

nolemonnomelon

出力例 2Copy

zzyxwvyz

入力例 3Copy

hhhhhqqqhhhhhjjhhhhhpppp

出力例 3Copy

zzzzzyyzzzzzxxxx