• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۱۲۸ مگابایت

---

چندی پیش سازمان اطلاعاتی جمهوری کره(ساجک) اعلام کرد با همکاری SSIS(Sharif Security Intelligence Service سازمان اطلاعات امنیت شریف، سیستم انتقال پیام ETA(گروهک تروریستی باسکی) را رمزگشایی کرده است. سیستم انتقال اطلاعات در این شبکه به طرز قابل تحسینی تر و تمیز و شگفت آور بود. این گروه براي انتقال یک متن، پس از انتقال خود کلمات پیام (که شیوه ي آن در این مسئله بررسی نمی شود)، ترتیب و جایگشت آن ها را تبدیل به یک رشته ي باینري می کرد که در عملیاتی ترین شرایط هم به سادگی قابل انتقال بود. (در آخرین مورد درگیري، جاسوس محاصره شده با دنباله اي از شلیک کردن/ نکردن با تفنگ خالیش، لو رفتن عملیات را به اعضاي گروهک خبر داد) در حقیقت، رشته ي باینري حاوي اطلاعات فرایند مرتب سازي ادغامی بر روي جایگشت اولیه و اصلی کلمات بود که در نهایت کلمات را به حالت مرتب شده در می آورد. گیرنده ي پیام، باید با مهندسی معکوس جایگشت اولیه از کلمات که در حقیقت اصل پیغام بوده را بازیابی می کرد. نحوه ي تولید رشته در شبه کد زیر توضیح داده شده است:

mergeSort(array a)
	array b = a.subarray (0, a.size / 2),
	array c = a.subarray(a.size() / 2, a.size())
	mergeSort(b)
	mergeSort(c)
	a = merge(b, c)
merge(array a, array b)
	do the famous merge method. in each step:
	if the element is chosen from a
		add '0' to the binary string
	else
		add 1 to the binary string

فرستنده در ابتدا تابع mergeSort را روي کل آرایه ي رشته ها (که همان متن اصلیست) صدا می زد و در نهایت با کد بالا، رشته‌ي دودویی مورد نظر تولید و آماده ي ارسال می گردد. کد رمزنگار رشته ها را هم با شیوه ي خاصی مقایسه و نهایتا مرتب می کرد. به این ترتیب که اگر یکی از رشته ها شامل زیررشتهmoji بود، زود تر از رشته ي دیگر می آید. کوچکی و بزرگی حروف مهم نیست؛ MojI یا mOJI هم همین طور هستند (کسی هنوز معناي دقیق این کلمه ي محلی را نمی داند!). اگر هر دو رشته این زیر دنباله را داشتند یا هر دو نداشتند رشته ها معمولی (lexicographically) مقایسه می شوند؛ به همان سیستمی که در لغتنامه ها لغت ها را مرتب می کنند. سازمان امنیت اطلاعات دانشگاه، بعد از رسانه اي کردن این موضوع براي بازیابی اطلاعات آرشیو شده از مکالمات رمزي این گروه، از شما یک برنامه ي رمزگشایی تقاضا کرده. شما باید با دریافت یک پیام رمزنگاري شده، اصل متن را بازیابی کنید.

ورودی

در ورودی ابتدا عدد n تعداد رشته ها ، و سپس به همین تعداد رشته، و سپس رشته‌ی دودویی که باید رمزگشایی شود می‌آید. رشته‌ها شامل حروف کوچک و بزرگ انگلیسی هستند و تعداد آن‌ها حداکثر ۱۰۰۰۰۰ تاست.

خروجی

در خروجی باید کلمات متن اصلی را هرکدام در یک خط چاپ کنید.

مثال

ورودی نمونه

7
ACSmojicLm
mOJICVKnHLYJs
NHCpGb
uRcGD
ZxMOjIC
cUUbXcf
RdEt
01110010101010010111

خروجی نمونه

NHCpGb
ACSmojicLm
ZxMOjIC
mOJICVKnHLYJs
cUUbXcf
RdEt
uRcGD