公式解説の \(T_{\infty}\) のような考察を通らない解法です．

一般に次の問題を考えてみます．

• \(k=1,2,\ldots,K\) に対して文字列からなる集合 \(X_k\) が与えらえている．
• 各 \(k\) から文字列 \(S_k\in X_k\) を選び結合する．得られる文字列が辞書順最小になるようにせよ．

文字列結合について \(B<C\iff A+B<A+C\) が成り立つことに注意すると，この問題は後ろから順に貪欲で最適化できます．つまり，

• \(\mathrm{ANS}\) を空文字列で初期化する．
• \(k=K,K-1,\ldots,1\) の順に，\(S_k+\mathrm{ANS}\) が辞書順最小になるような \(S_k\in X_k\) を選び，\(\mathrm{ANS}\) を \(S_k+\mathrm{ANS}\) に置き換える．

あとは次のような内容を実装すれば AC できます．

• 固定された長さに対しては辞書最小の文字列しか使わないとしてよいことは明らかである．これを使って入力文字列を \(10\) 個以下にしておく．
• rolling hash を用いて \(\mathrm{ANS}\) の prefix のハッシュを計算できる状態を維持する．\(S+\mathrm{ANS}\) の類の辞書順比較は，ハッシュの取得と二分探索によって lcp を計算することで行う．

\(\mathrm{ANS}\) の先頭に文字を追加していくため，場合によっては \(\mathrm{reverse(ANS)}\)を管理するような実装方針の方が簡潔になるかもしれません．以下の提出はそのような実装方針で，比較では rolling hash を用いて suffix の共通文字列長を計算しています．

【解答例（コンテスト中の提出） 】 https://atcoder.jp/contests/abc416/submissions/67929192