ove
lovely
loly
lovely
DNA ardıcıllığı üzərində tədqiqat aparan kompyuter alimi, Tomasın, verilmiş cüt sətirlərin ən böyük altsətirlərini hesablamaq ehtiyacı var. Hesab edin ki, hərflərdən və w=a_1a_2 …a_r sözlərindən ibarət Σ əlifbasında i = 1, 2, …,r üçün a_i ∈ Σ. w altardıçıllığı isə 1 ≤ i_1 < i_2 < … < i_s ≤ r üçün x=a_i_1a_i_2 …a_is. x altardıçıllığı əgər j = 1, 2, …, s-1 üçün i_j_{+1}=i_j + 1 olarsa, w seqmentidir. Məsələn, sözü sözünün seqmentidir, lakin sözü sözünün altardıcıllığıdır, seqmenti deyil.
lovxxelyxxxxx
xxxxxxxlovely
lovely
xxxxxxx
Söz iki w_1 və w_2 sözlərinin o zaman sadə altardıcıllığı olar ki, o hər iki sözün altardıcıllığı olsun. w_1 və w_2 sözlərinin ən uzun sadə altardıcıllığı mümkün ən uzun sadə altardıcıllıqdır. Məsələn, hesab edək ki, w_1= və w_2= sözlərdir. w_3= və uzunluğu 7 hərf olan w_4= sözlərinin hər ikisi w_1 və w_2-nin sadə altardıcıllığıdır. Faktik olaraq, w_4 onların ən böyük sadə altardıcıllığıdır. Qeyd etmək lazımdır ki, uzunluğu sıfır olan boş sətir, baxmayaraq ki, ən uzun deyil, həmişə sadə altadıcıllıqdır.
lovely
lovxxelyxxxxx
xxxxxxxlovely
xxxxxxx
Tomasın bu variantında əlavə tələb qoyulur: altardıcıllıq uzunluğu K olan sadə seqmentdən təşkil olunmalıdır. Məsələn, əgər Tomas K=3 olduğunu qərara alırsa, onda razılaşır ki, sözü və sözlərinin məqbul sadə altardıcıllığıdır, halbu ki, uzunluğu 7 və eyni zamanda sadə altardıcıllıq olan , məqbul deyildir. Siz Tomasa kömək edə bilərsinizmi?
Giriş verilənləri bir neçə test variantını ehtiva edir. Testin ilk sətri sadə seqmentlərin minimum uzunluğunu göstərən k tam ədədini ehtiva edir, burada 1 ≤ K ≤ 100. Növbəti iki sətir normal 26 hərfdən ibarət olan əlifbanın kiçik hərflərindən təşkil olunmuş hər iki sətri ehtiva edir. Hər bir sətrin l uzunluğu üçün 1 ≤ l ≤ 10^3 doğrudur. Giriş verilənlərində hər hansı bir sətirdə boşluqlar yoxdur. Giriş verilənlərinin sonu 0 ehtiva edən sətirlə tamamlanır.
Hər bir test variantı üçün Sizin proqram hər iki sətirdən ən azı K uzunluqda ən böyük sadə altardıcıllığın uzunluğundan ibarət ardıcıl seqmentlərdən təşkil olunmuş yeganə sətir çap etməlidir. Əgər uzunluğu 0-dan böyük olmayan sadə altardıcıllıq yoxdursa, 0 çap etməlidir.