Общая подстрока

Заданы две строки s, t и целое число k. Рассмотрим множество всех таких непустых строк, которые встречаются как подстроки в s и t одновременно.

Найдите k-ую в лексикографическом порядке строку из этого множества.

Входные данные

В первых двух строках записаны строки s и t (1 ≤ |s|, |t| ≤ 10^5). В третьей строке записано целое число k (1 ≤ k≤ 10^18).

Строки состоят из маленьких латинских букв.

Выходные данные

В первой строке выведите искомую строку или -1, если такой не существует.

Примеры