Ortaq alt sətir

Verilmiş iki sətir s və t və tam ədəd k ilə bağlı bir problem var. s və t sətirlərində eyni zamanda alt sətir kimi mövcud olan bütün boş olmayan alt sətirlərin çoxluğunu nəzərdən keçirək.

Bu çoxluqdan leksikoqrafik ardıcıllıqla k-cı sətiri tapın.

Giriş verilənləri

İlk iki sətirdə s və t sətirləri verilmişdir (1 ≤ |s|, |t| ≤ 10^5). Üçüncü sətirdə tam ədəd k verilmişdir (1 ≤ k ≤ 10^18).

Sətirlər yalnız kiçik latın hərflərindən ibarətdir.

Çıxış verilənləri

Birinci sətirdə axtarılan sətiri və ya belə bir sətir mövcud deyilsə -1 çıxarın.

Nümunələr