Спільний підрядок

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

Рядок S менше рядка T у лексикографічному порядку, якщо виконується одна з двох умов:

• S є префіксом T;

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

Вхідні дані

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

Вихідні дані

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

Приклади