Задача BrokenTasks
Учасникам літньої школи нарешті роздали завдання з фізики! Шкода тільки, що через спеку піт з лоба Влада розмочив чорнила і тепер складно розібрати деякі букви. Влад вирішив замінити незрозумілі букви на символи решітки і запитатися в Віталія Юрійовича, які букви мають бути на цих місцях. Однак Віталій Юрійович точно не пам'ятав умови, тому для кожної позиції вибрав K (1 <= K <= 26) можливих букв. Влад вже почав сумувати, але Віталій Юрійович згадав, що серед усіх можливих варіантів потрібний знаходиться на X-вому (1 <= X <= 10^9) місці серед всіх відсортованих в алфавітному порядку слів. Влад вже впорався з цією задачею, а чи зможете ви?
Технічні умови:
Програма brokentasks читає з клавіатури (стандартного пристрою введення) чотири натуральних числа N, M, K, X - довжину "зіпсованого" слова, кількість незрозумілих позицій, кількість варіантів для кожної позиції і номер правильного слова в алфавітному порядку. Далі програма читає зіпсоване слово, після чого читає M стрічок, в кожній з яких знаходяться набори можливих символів для кожної з позицій. Кожен набір містить K різних букв.
Зіпсоване слово складається лише з малих латинських букв та символів "#". Набори складаються виключно з малих латинських букв.
Програма brokentasks виводить на екран (стандартний пристрій виведення) єдину стрічку - правильне слово. Гарантується, що слово існує.
Введення
Виведення
7 2 3 7
ph#s#cs
iay
yoi
physics
Примітка: можливі слова (в алфавітному порядку): phasics, phasocs, phasycs, phisics, phisocs, phisycs, physics, physocs, physycs