Məsələlər
DNA Subsequences
DNA Subsequences
\textbf{ove}
\textbf{lovely}
\textbf{loly}
\textbf{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ə \textit{\textbf{w}}\textbf{=}\textit{\textbf{a}}\textbf{_1}\textit{\textbf{a}}\textbf{_2 …}\textit{\textbf{a_r}} sözlərindən ibarət \textbf{Σ} əlifbasında \textit{\textbf{i}} = \textbf{1}, \textbf{2}, …,\textit{\textbf{r}} üçün \textit{\textbf{a_i}} ∈ \textbf{Σ}. \textit{\textbf{w}} \textit{altardıçıllığı isə } \textbf{1} ≤ \textit{\textbf{i}}\textbf{_1} < \textit{\textbf{i}}\textbf{_2} < … < \textit{\textbf{i_s}} ≤ \textit{\textbf{r}} üçün \textit{\textbf{x}}\textbf{=}\textit{\textbf{a_i}}\textbf{_1}\textit{\textbf{a_i}}\textbf{_2 …}\textit{\textbf{a_is}}. \textit{\textbf{x }}\textit{altardıçıllığı} əgər \textit{\textbf{j}} = \textbf{1}, \textbf{2}, …,\textit{ }\textit{\textbf{s}}\textbf{-1 }üçün\textbf{ }\textit{\textbf{i_j}}\textbf{_\{+1\}=}\textit{\textbf{i_j}}\textbf{ + 1} olarsa\textbf{, }\textit{\textbf{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.
\textbf{lovxxelyxxxxx}
\textbf{xxxxxxxlovely}
\textbf{lovely}
\textbf{xxxxxxx}
Söz iki \textit{\textbf{w}}\textbf{_1} və \textit{\textbf{w}}\textbf{_2} sözlərinin o zaman sadə altardıcıllığı olar ki, o hər iki sözün altardıcıllığı olsun. \textit{\textbf{w}}\textbf{_1} və \textit{\textbf{w}}\textbf{_2} sözlərinin \textit{ən uzun sadə altardıcıllığı }mümkün ən uzun\textit{ sadə altardıcıllıqdır. }Məsələn, hesab edək ki, \textit{\textbf{w}}\textbf{_1=} və \textit{\textbf{w}}\textbf{_2=} sözlərdir. \textit{\textbf{w}}\textbf{_3=} və uzunluğu \textit{\textbf{7}} hərf olan \textit{\textbf{w}}\textbf{_4=} sözlərinin hər ikisi \textit{\textbf{w}}\textbf{_1} və \textit{\textbf{w}}\textbf{_2}-nin sadə altardıcıllığıdır. Faktik olaraq, \textit{\textbf{w}}\textbf{_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.
\textbf{lovely}
\textbf{lovxxelyxxxxx}
\textbf{xxxxxxxlovely}
\textbf{xxxxxxx}
Tomasın bu variantında əlavə tələb qoyulur: altardıcıllıq uzunluğu \textit{\textbf{K}} olan sadə seqmentdən təşkil olunmalıdır. Məsələn, əgər Tomas \textit{\textbf{K}}\textbf{=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 \textit{\textbf{7}} və eyni zamanda sadə altardıcıllıq olan , məqbul deyildir. Siz Tomasa kömək edə bilərsinizmi?
\InputFile
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 \textit{\textbf{k}} tam ədədini ehtiva edir, burada \textbf{1} ≤ \textit{\textbf{K}} ≤ \textbf{100}. Növbəti iki sətir normal \textit{\textbf{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 \textit{\textbf{l}} uzunluğu üçün \textbf{1} ≤ \textit{\textbf{l}} ≤ \textbf{10^3} doğrudur. Giriş verilənlərində hər hansı bir sətirdə boşluqlar yoxdur. Giriş verilənlərinin sonu \textit{\textbf{0}} ehtiva edən sətirlə tamamlanır.
\OutputFile
Hər bir test variantı üçün Sizin proqram hər iki sətirdən ən azı \textit{\textbf{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 \textit{\textbf{0}}-dan böyük olmayan sadə altardıcıllıq yoxdursa, \textit{\textbf{0}} çap etməlidir.
Giriş verilənləri #1
3 lovxxelyxxxxx xxxxxxxlovely 1 lovxxelyxxxxx xxxxxxxlovely 3 lovxxxelxyxxxx xxxlovelyxxxxxxx 4 lovxxxelyxxx xxxxxxlovely 0
Çıxış verilənləri #1
6 7 10 0