Fișierul intrare/ieșire	tensor.in, tensor.out	Sursă	Ural Regional School Programming Contest 2013
Autor	Ilya Kuchumov	Adăugată de	Spatarel Dan-Constantin • spatarel
Timp de execuție pe test	0.05 sec	Limită de memorie	16384 KB
Scorul tău	N/A	Dificultate	3.25

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Tensor

E anul 2031. Mult așteptatul moment al singularității tehnologice a avut loc și calculatoarele s-au răsculat împotriva oamenilor. Singura șansă a umanității sunt organismele inteligente modificate genetic, specializate în război, care ni s-au aliat în luptă. Evident, mașinile nu au încetat să se dezvolte și creează roboți tot mai distructivi. Între timp oamenii caută noi și noi secvențe ADN care să-i facă pe mutanți mai puternici și mai rezistenți.

De exemplu, Profesorul Yerfalomeus Ben a anunțat recent că doi mutanți pot fi comparați ca putere dacă li se cunosc ADN-urile. În acest scop, cele două secvențe ADN trebuie scrise ca șiruri de caractere ale alfabetului englez (oamenii de știință din viitor au introdus noi baze, pe lângă cele 4 deja cunoscute). S-a constatat că mutantul X este mai puternic decât mutantul Y dacă secvența ADN a mutantului X este mai mică lexicografic decât secvența ADN a mutantului Y.

Acum profesorul Ben vrea să facă un experiment. El are în laborator secvența ADN a unui mutant și mai mulți modificatori genetici. Un modificator genetic este o substanță care modifică o secvență ADN. Fiecare modificator genetic este descris printr-o literă mică a alfabetului englez. Profesorul Ben poate folosi modificatorii genetici în orice ordine și poate realiza una dintre următoarele operații cu fiecare dintre ei:

• Inserează un modificator genetic în secvența ADN (între două litere consecutive, înainte de prima literă sau după ultima literă);
• Alege o poziție din secvența ADN care conține o literă identică cu modificatorul genetic, șterge litera respectivă din secvență și distruge modificatorul genetic.

Termenul de valabilitate al modificatorilor genetici va expira în curând, astfel că profesorul Ben vrea să folosească toți modificatorii genetici din laborator. Cum ar trebui să-i folosească astfel încât să obțină din secvența ADN inițială o secvență ADN a unui mutant cât mai puternic posibil?

Date de intrare

Fișierul de intrare tensor.in conține pe prima linie secvența ADN inițială. A doua linie conține lista de modificatori genetici disponibili.

Date de ieșire

În fișierul de ieșire tensor.out trebuie să apară secvența ADN minimă lexicografică ce poate fi obținută prin utilizatoarea tuturor modificatorilor genetici.

Restricții

• Ambele șiruri de caractere din fișierul de intrare sunt nevide, formate numai din litere mici ale alfabetului englez și au o lungime mai mică de 100 000 de caractere.
• Se garantează că este imposibil să obținem șirul vid din secvența ADN inițială folosind toți modificatorii genetici.

Exemplu

Explicație

abc —b-> abbc —b-> abc —c-> ab