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

Заданы две строки, состоящие из 0 и 1. Рассмотрим все строки, которые являются подстроками обеих данных строк. Найдите среди них k-ую в лексикографическом порядке.

Строка S меньше строки T в лексикографическом порядке, если выполняется одно из двух условий:

• S является префиксом T;

• существует i, не превышающее длин строк S и T, такое, что для j < i выполняется S[j] = T[j] и S[i] < T[i].

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

Первые две строки входного файла содержат заданные строки, длиной не более 4000 символов каждая. Третья строка содержит целое положительное число k, не превышающее количества общих подстрок двух заданных строк.

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

Выведите в выходной файл k-ую в лексикографическом порядке общую подстроку заданных строк.

Примеры