На вашем заводе производят два вида цветной бумаги: красную и синюю. На каждой красной бумаге написана строка $S$: она состоит из $|S|$ единичных квадратов, расположенных в ряд, при этом $S_i$ написано на $i$-м квадрате слева. На каждой синей бумаге написана строка $T$: она состоит из $|T|$ единичных квадратов, расположенных в ряд, при этом $T_i$ написано на $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