Заданы две строки s, t и целое число k. Рассмотрим множество всех таких непустых строк, которые встречаются как подстроки в s и t одновременно.
Найдите k-ую в лексикографическом порядке строку из этого множества.
В первых двух строках записаны строки s и t (1 ≤ |s|, |t| ≤ 10^5). В третьей строке записано целое число k (1 ≤ k≤ 10^18).
Строки состоят из маленьких латинских букв.
В первой строке выведите искомую строку или -1, если такой не существует.