+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۱۲۸ مگابایت ---------- چندی پیش سازمان اطلاعاتی جمهوری کره(ساجک) اعلام کرد با همکاری `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 ```