あなたの工場では、赤色と青色の2種類の色の紙を製造しています。

各赤色の紙には文字列 $S$ が書かれています。これは $|S|$ 個の単位正方形が横一列に並んだものであり、左から $i$ 番目の正方形には $S_i$ が書かれています。

各青色の紙には文字列 $T$ が書かれています。これは $|T|$ 個の単位正方形が横一列に並んだものであり、左から $i$ 番目の正方形には $T_i$ が書かれています。

あなたは、赤色の紙と青色の紙から「二色紙（double-colored paper）」と呼ばれる新しい種類の紙を作ることを計画しています。これを作るには、赤色の紙から正の整数長の連続する部分を切り出し、青色の紙からも同様に切り出します。その後、赤色の断片の末尾と青色の断片の先頭を貼り合わせます。

例えば、$S$ が abcde、$T$ が fghij であるとします。このとき、bcdfg や abcij といった文字列が書かれた二色紙を作ることができます。しかし、acdghij や fghij といった文字列が書かれた二色紙を作ることはできません。（ここで、下線が引かれた文字列は赤色の断片を、残りは青色の断片を表します。）2つの二色紙は、書かれている赤色の文字列と青色の文字列がそれぞれ同じであれば、同一のものとみなされます。

作ることができるすべての異なる二色紙の中で、書かれている文字列が辞書順で $K$ 番目に小さいものを求めたいと考えています。なお、書かれている文字列は同じであっても、赤色の紙の長さが異なる紙が存在する場合がありますが、その場合は任意に順序付けて構いません。

入力

1行目に文字列 $S$ が与えられます。 2行目に文字列 $T$ が与えられます。 3行目に整数 $K$ が与えられます。

• $1 \le |S| \le 75\,000$
• $1 \le |T| \le 75\,000$
• $S$ および $T$ は英小文字からなる
• $1 \le K \le 8 \cdot 10^{18}$

出力

作ることができる二色紙の総数が $K$ 未満である場合は $-1$ を出力してください。 それ以外の場合は、作ることができるすべての二色紙の中で、書かれている文字列が辞書順で $K$ 番目に小さいものを出力してください。

入出力例

入力 1

tww
wtw
21

出力 1

wwtw