4. Sladké náramky

Ak nevieš programovať, nezúfaj! Môžeš sa to naučiť a ešte za to získať body, ktoré sa ti budú počítať namiesto tejto úlohy.

Stačí, že pôjdeš na stránku Programátorskej Liahne (liahen.ksp.sk). Keď budeš riešiť sadu variables_cpp, bodmi, ktoré získaš si môžeš nahradiť riešenie tejto úlohy. Stačí ak na spodku tejto stránky odovzdáš pdf-ko s prezývkou, ktorú používaš na Liahni.

Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Jitke na [email protected]

V jedno pekné popoludnie sa Timka vracala celá šťastná domov zo sústredenia Prasku. Nielenže bolo sústredenie skvelé, tešila sa aj z dvoch náramkov plných cukríkov všelijakých chutí, ktoré vyhrala v tombole.

Aby spravila radosť Romanovi, ktorý na sústredenie nemohol prísť, rozhodla sa, že mu vyrobí nový špeciálny náramok. Tento náramok by mal byť čo najdlhší a zároveň by malo platiť, že cukríky, z ktorých bude zložený, sa budú dať preusporiadať tak, aby tvorili podpostupnosť (pozri časť Úloha) jedného z pôvodných náramkov. A to nie je všetko! Ak cukríky znovu preusporiadame, vytvoria podpostupnosť druhého z pôvodných náramkov.

Timka, ešte nabudená zo sústredka, hneď vedela, z ktorých cukríkov má náramok pre Romana poskladať. Len čo prišla domov pustila sa do práce a aj zabudla, akú mala sama na cukríky chuť.

Úloha

Vašou úlohou je napísať program, ktorý na vstupe dostane popis náramkov, ktoré Timka vyhrala a vypíše náramok, ktorý Timka vyrobila pre Romana.

Pre jednoduchosť si budeme cukríky reprezentovať malými písmenami anglickej abecedy – rovnaké písmená predstavujú rovnaké cukríky. Náramok si teda vieme predstaviť ako reťazec písmen, napr. abac je náramok so štyrmi cukríkmi, kde sú prvý a tretí cukrík rovnaké.

Romanov náramok musí byť najdlhší možný. Navyše cukríky v ňom musíme vedieť preusporiadať tak, aby vytvorili podpostupnosť prvého náramku, a potom preusporiadať tak, aby vytvorili podpostupnosť druhého náramku.

Podpostupnosť reťazca dostaneme tak, že z neho vymažeme ľubovoľné znaky a zostávajúce písmená bez zmeny poradia spojíme dokopy. Napríklad nrm, ramo, naok sú podpostupnosti slova naramok, ale aaa ani kom nie sú.

Samozrejme, môže existovať viac možností ako vytvoriť náramok pre Romana, nás preto bude zaujímať lexikograficky najmenší. Teda ak by sme zobrali všetky možné prípustné najdlhšie náramky a zoradili by sme ich podľa abecedy, tento by bol prvý v poradí.

Formát vstupu

Na prvom riadku vstupu je reťazec reprezentujúci prvý Timkin náramok. Na druhom riadku je reťazec reprezentujúci druhý náramok.

Formát výstupu

Na výstup vypíšte do jediného riadku lexikograficky najmenší reťazec, ktorý tvorí najdlhší možný náramok pre Romana. V prípade, že takýto náramok neexistuje, vypíšte neda sa.

Hodnotenie

Príklady

Input:

prask
trojsten

Output:

rs

Náramok rs je podpostupnosťou náramku prask (cukríky na indexoch \(1\) a \(3\)) a aj podpostupnosťou náramku trojsten (cukríky na indexoch \(1\) a \(4\)).

Input:

krk
nos

Output:

neda sa

Timka nedokáže vyrobiť špeciálny náramok pre Romana.

Input:

hlava
aha

Output:

aah

Aj náramok haa by spĺňal požiadavky, čo sa týka dĺžky a podpostupností (v prvom náramku cukríky na indexoch \(0\), \(2\) a \(4\). V druhom náramku sa preusporiadanie aha zhoduje s cukríkmi na indexoch \(0\),\(1\) a \(2\)), no nebol by lexikograficky najmenší. Preto vypisujeme náramok aah.