Problem
در یکی از شبکه های تلویزیونی، قرعه کشی بعدی هر هفته برگزار می شود. در طول هفته، شرکت کنندگان شرط بندی می کنند. هر شرط شامل نامگذاری یک عدد M رقمی در سیستم اعداد K پایه است (یعنی در واقع، هر شرکت کننده M رقم را نامگذاری می کند، که هر یک از آنها در محدوده 0 تا K و منهای 1 قرار دارد). صفرهای ابتدایی در اعداد مجاز هستند.
در مرحله ای، شرط بندی بر روی قرعه کشی فعلی به پایان می رسد و پس از آن، مجری شماره برنده را در تلویزیون اعلام می کند (این نیز یک عدد M رقمی در سیستم اعداد K-ary است). پس از آن، آن دسته از بینندگان تلویزیونی که رقم اول شماره آنها با اولین رقم شماره نامگذاری شده توسط میزبان مطابقت دارد، برنده ای به مبلغ A
1 روبل دریافت می کنند. کسانی که دو رقم اول — A
2 روبل دریافت کنید (در همان زمان، اگر بازیکن رقم دوم مطابقت داشته باشد، اما رقم اول مطابقت نداشته باشد، چیزی دریافت نمی کند). به همین ترتیب، کسانی که سه رقم اول را حدس زدند A
3 روبل دریافت می کنند. و غیره. کسانی که تعداد کل را حدس زدند به طور کامل روبل Am دریافت می کنند. علاوه بر این، اگر بازیکن اولین رقم t را حدس بزند، A
t روبل دریافت می کند، اما برای حدس زدن t−1، t−2 و غیره جوایزی دریافت نمی کند. ارقام اگر بازیکن شماره اول را حدس نزند، چیزی دریافت نمی کند.
برنامه‌ای بنویسید که با توجه به شرط‌بندی‌های مشخصی که بینندگان انجام می‌دهند، شماره‌ای را که مجری تلویزیون باید نامگذاری کند تا شرکت برگزارکننده حداقل مبلغ را به عنوان برنده پرداخت کند، پیدا کند. برای راحتی شما، شرط بندی های انجام شده توسط بازیکنان قبلاً به ترتیب غیر نزولی مرتب شده اند.
ورودی
خط اول شامل اعداد N (تعداد بینندگان تلویزیونی است که شرط‌بندی کرده‌اند، 1N100000)، M (طول اعداد 1M10) K (پایه سیستم اعداد 2 ≤ K ≤ 10). خط بعدی حاوی M اعداد صحیح A
1، A
2، ...، A
M است، که پرداخت‌ها را مشخص می‌کند اگر فقط دو مورد اول، اول، ... , همه ارقام (1 ≤ A
1 ≤ A
2 ≤ ... ≤ A
M ≤ 100000 ) . هر یک از N خطوط بعدی شامل یک عدد K-اری M رقمی است. اعداد به ترتیب غیر کاهشی هستند.
حصر
در خط اول شماره مورد نظر را چاپ کنید (در صورت وجود چندین راه حل — هر کدام را چاپ کنید) و در خط دوم — مبلغی که هنگام نام بردن از مجری تلویزیون در روز اول باید به عنوان برنده پرداخت شود.
نمونه‌ها
<سر>
| # |
ورودی |
خروجی |
<بدن>
| 1 |
10 3 2
1 3 100
000
000
001
010
100
100
100
100
110
111 |
011
6 |
| 2 |
1 1 10
100
0 |
1
0 |