在你的工厂里，你正在生产两种颜色的纸，一种是红色的，另一种是蓝色的。

每张红纸上都写有一个字符串 $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