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