Заданы две строки, состоящие из 0 и 1. Рассмотрим все строки, которые являются подстроками обеих данных строк. Найдите среди них k-ую в лексикографическом порядке.
Строка S меньше строки T в лексикографическом порядке, если выполняется одно из двух условий:
S является префиксом T;
существует i, не превышающее длин строк S и T, такое, что для j < i выполняется S[j] = T[j] и S[i] < T[i].
Первые две строки входного файла содержат заданные строки, длиной не более 4000 символов каждая. Третья строка содержит целое положительное число k, не превышающее количества общих подстрок двух заданных строк.
Выведите в выходной файл k-ую в лексикографическом порядке общую подстроку заданных строк.