D - Han Burger Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

N 個の文字あるいは文字列 X_1, X_2, \dots, X_N をこの順に連結させた文字列を X_1 + X_2 + \cdots + X_N と表記します。
文字列に対して、バーガー、全バーガー、半バーガーを以下のように定義します。この定義はE問題と同じです。

  • バーガーとは、全バーガーである文字列、および半バーガーである文字列
  • 全バーガーとは、あるバーガー A とある文字 c に対して、c + A + c と書ける文字列、および空文字列
  • 半バーガーとは、ある空でないバーガー A、B に対して、A + B と書ける文字列のうち、全バーガーでない文字列

例えば、abba や abbcca は全バーガー、aabb や abbacc は半バーガーですが、abbcbbc や ababa はバーガーではありません。

英小文字からなる文字列 S に対し、S + T が全バーガーとなるような、英小文字からなる文字列 T が存在するとき、|T| が最小である T のうち辞書順で最小のものを出力してください。そのような T が存在しないときは -1 を出力してください。

辞書順とは ? 文字列 S = S_1S_2 \cdots S_{|S|} が文字列 T = T_1T_2 \cdots T_{|T|} より 辞書順で小さい とは、下記の 1. と 2. のどちらかが成り立つことを言います。ここで、|S|, |T| はそれぞれ S,T の長さを表します。
  • 1. |S| < |T| かつ S = S_1S_2 \cdots S_{|S|} = T_1T_2 \cdots T_{|S|}。
  • 2. ある整数 1 \leq i \leq \min\{|S|, |T|\} が存在して、下記の 2 つがともに成り立つ。
    • S = S_1S_2 \cdots S_{i-1} = T_1T_2 \cdots T_{i-1}
    • S_i が T_i よりアルファベット順で小さい文字である。

制約

  • 1 \leq |S| \leq 200{,}000
  • S は英小文字からなる文字列

小課題

  1. ( 1 点) S は a と b からなり、|S| \leq 10 となる文字列

  2. ( 99 点) 追加の制約はない

入力

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

S

出力

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

入力例 1

abcca

出力例 1

aba

T = aba とすると、S+T = abccaaba は全バーガーとなります。
条件を満たす T は aba 以外にも考えられますが、2 文字以下であるものは存在せず、3 文字である T のうち辞書順で最も小さいのは aba であるため、aba を出力します。

このテストケースは小課題 1 の制約を満たしません。

入力例 2

abba

出力例 2



T を空文字列にすれば、S+T = abba は全バーガーとなります。


このテストケースは小課題 1 の制約を満たします。