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

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

Знайдіть k-ий у лексикографічному порядку рядок з цієї множини.

Вхідні дані

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

Рядки складаються з маленьких латинських літер.

Вихідні дані

У першому рядку виведіть шуканий рядок або -1, якщо такого не існує.

Приклади