Masala #0927

Xotira 16 MB Vaqt 1000 ms
14

Start up nomlash

Shohrux va Jasur juda qalin do‘stlar. Lekin baʼzida ular oddiy narsalar ustida ham tortishib turishadi. Yaqinda ular start up loyiha boshlashdi va unga nom berish ustida tortishib qolishdi. Bu muommoni hal qilish maqsadida bir qiziqarli o'yin o'ylab topishdi.

Ikki do'st har ikkalasi ixtiyoriy \(n\) ta belgidan tashkil topgan to'plamni tanlaydi(belgilar takrorlangan bo'lishi mumkun). Dastlab loyihaning nomi \(n\) ta \(?\) belgisidan iborat va ular nabat bilan o'zidagi to'plamdan bir belgini olib istalgan \(?\) begini o'rniga joylashtiradi.

O'yinni Shohrux boshlaydi va u loyihaning nomi imkon qadar liksografik jihatdan kichik bo'lishini, Jasur esa liksografik jihatdan katta bo'lishi istaydi. Agar ikkisi ham optemal o'ynasa loyiha nomi nima bo'lishini aniqlang.


Kiruvchi ma'lumotlar:

Alohida qatorlarda \(s_1,s_2(1\leq |s_1|,|s_2|\leq3*10^5; |s_1|=|s_2|)\) lotin alifbosining kichik harflaridan tashkil topgan satrlar beriladi.


Chiquvchi ma'lumotlar:

Shohrux va Jasur hosil qilgan loyiha nomini chop eting.


Misollar
# input.txt output.txt
1
ioi
imo
ioi
2
olex
iows
ewls
Izoh:

1-test: Shohrux {\(i, o, i\)} to'plamni, Jasur {\(i, m, o\)} to'plamni tanlaydi. Loyiha nomi dastlab \(???\) ga teng. Shohrux birinchi \(?\) belgisini o'rniga o'zidagi to'plamdan \(i\) ni joylashtiradi hozirda loyiha nomi \(i??\), Jasur esa  ikkinchi \(?\) belgisini o'rniga \(o\) harfini joylashtiradi \(io?\) va Shohrux uchunchi \(?\) belgisini o'rniga \(i\) belgisini joylashtiradi hosil bo'lgan loyiha nomi \(ioi\).