eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Нове слово у рекламі

Нове слово у рекламі

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

У наші дні надання поверхонь огорож та стін промислових будівель рекламодавцям – уже не оригінальний спосіб отримати додатковий зарабіток, а дещо таке, що саме собою разуміється.

Невелика компанія "Домострой" також вирішила вийти на цей рынок і почала пропонувати місце для реклами на своїх блоках огорож. Блок являє собою параллелепіпед розміром 1×1×L, на одній зі сторін якого є місце для реклами – простір розміру 1×L, в у який можна вписати рівно L букв латинського алфавіту.

На жаль, іноді угоди у компанії зривались, і наперед підготовлені блоки з рекламою відправлялись на склад. З часом там накопилась солідна кількість блоків різних типів (блоки різних типів відрізняються один від одного лише написом), тому було вирішено використати їх повторно.

Була запропонована наступна ідея: якщо поставить декілька блоків один на одного, то, читаючи зверху донизу і зліва направо, можна буде прочитати який-небудь інший текст, як показано на рисунку.

Таким чином, можна отримати рекламний напис для нового клієнта. При цьому з естетичних міркувань при прочитанні кінцевого напису розриви у вигляді зафарбованих букв недопустимі.

Опишемо цей процес більш формально. Після того, як деяке число K блоків, кожен з яких має довжину L, поставили один на одного, отримали прямокутну таблицю розміром K×L, у кожній клітинці якої знаходиться буква латинського алфавіту. Кожен рекламний блок відповідає рядку цієї таблиці. Тепер вміст цієї таблиці виписується по стовбцям, починаючи з самого лівого. При цьому у кожному стовбці букви виписуються зверху вниз. У випадку, зображеному на рисунку, в результаті цьго процесу получився б рядок "TOEIIZENITKN". Необхідно, щоб рекламний напис, необхідний замовнику, входив у отриманий рядок як підрядок: "TOEIIZENITKN".

Потрібно написати програму, яка будет визначати, яку мінімальну кількість блоків потрібно використати, щоб отримати рекламний напис, необхідний замовнику. При цьому можна вважати, що на складі блоків кожного типу необмежено багато.

Вхідні дані

Перший рядок вхідного файлу містить два натуральних числа N та L – число різних типів блоків на складі та довжина кожного блоку відповідно (1N100, 1L100). Наступні N рядків містять по одному запису довжиною L, який складається з рядкових латинських букв – написи на блоках відповідного типу. Написи на блоках різних типів не співпадають.

Останній рядок вхідного файлу містить новий рекламний напис s – рядок, який складається лише з рядкових латинських букв (1|s|200). Можна вважати, що на складі знаходиться необмежене число блоків кожного типу.

Вихідні дані

У першому рядку вихідного файлу необхідно вивести натуральне число K – мінімальну кількість блоків, які потрібно використати для складання нової реклами. Наступний рядок повинен містити K чисел – номери типів блоків, які потрібно для цього використати, перераховуючи їх зверху вниз. Типи блоків нумеруються з одиниці у порядку їх задання у вхідному файлі.

Якщо відповідей декілька, виведіть довільну з них. Якщо розв'язку не існує, виведіть у вихідний файл число –1.

Приклад

Вхідні дані #1
1 1
a
a
Вихідні дані #1
1
1