在你的工廠中，你正在製作兩種顏色的紙，一種是紅色，另一種是藍色。

每張紅色的紙上都寫有一個字串 $S$：它由 $|S|$ 個單位正方形排成一列組成，第 $i$ 個正方形（從左邊數起）上寫著 $S_i$。

每張藍色的紙上都寫有一個字串 $T$：它由 $|T|$ 個單位正方形排成一列組成，第 $i$ 個正方形（從左邊數起）上寫著 $T_i$。

你計畫用紅色和藍色的紙製作一種稱為「雙色紙」的新紙張。製作方法是：你將紅色紙剪下一段長度為正整數的連續部分，然後對藍色紙做同樣的操作。之後，將紅色紙片的末端與藍色紙片的開頭黏在一起。

例如，假設 $S$ 為 abcde 而 $T$ 為 fghij。你可以製作出寫有 bcdfg 或 abcij 的雙色紙。然而，你不能製作出寫有 acdghij 或 fghij 的雙色紙。（此處底線字串表示紅色紙片，其餘部分表示藍色紙片。）如果兩張雙色紙上的紅色字串相同且藍色字串也相同，則視為相同。

在所有可以製作出的不同雙色紙中，你想要找出寫在上面且字典序第 $K$ 小的字串。注意，可能存在寫有相同字串但紅色紙片長度不同的紙張：在這種情況下，你可以任意排序它們。

輸入格式

第一行包含字串 $S$。 第二行包含字串 $T$。 第三行包含整數 $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