Задача H регионального тура (online тестирование). Новое слово в рекламе

Первоисточник: Региональный этап Всероссийской олимпиады школьников по информатике 2009 - 2010 учебного года

Задачу добавил: alef

Успешно сдано решений: 6

Имя входного файла: input.txt
Имя выходного файла: output.txt
Максимальное время работы на одном тесте: 2 c
Максимальный объем используемой памяти: 64 Мб
Максимальная оценка: 100 баллов

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

Небольшая компания «Домострой» также решила выйти на этот рынок и стала предлагать место для рекламы на своих блоках заборов. Блок представляет собой параллелепипед размером 1×1×L, на одной из сторон которого есть место для рекламы – пространство размера 1×L, в которое можно вписать ровно L букв латинского алфавита.

К сожалению, иногда сделки у компании срывались, и заранее подготовленные блоки с рекламой отправлялись на склад. Со временем там скопилось приличное количество блоков различных типов (блоки разных типов отличаются друг от друга только надписью), поэтому было решено использовать их вторично.

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

Таким образом, можно получить рекламную надпись для нового клиента. При этом из эстетических соображений при прочтении конечной надписи разрывы в виде закрашенных букв недопустимы.

После того, как некоторое число K блоков, каждый из которых имеет длину L, поставили друг на друга, получилась прямоугольная таблица размером K×L, в каждой клетке которой находится буква латинского алфавита. Каждый рекламный блок соответствует строке этой таблицы. Теперь содержимое этой таблицы выписывается по столбцам, начиная с самого левого. При этом в каждом столбце буквы выписываются сверху вниз. В случае, изображенном на рисунке, в результате этого процесса получилась бы строка «TOEIIZENITKN». Необходимо, чтобы рекламная надпись, требуемая заказчику, входила в получившуюся строку как подстрока «TOEIIZENITKN».

Требуется написать программу, которая будет определять, какое минимальное количество блоков надо использовать, чтобы получить рекламную надпись, необходимую заказчику. При этом можно считать, что на складе блоков каждого типа неограниченно много.

Формат входных данных

Первая строка входного файла входного файла содержит два натуральных числа N и L – число различных типов блоков на складе и длина каждого блока соответственно (1 ≤ N ≤ 100, 1 ≤ L ≤ 100). Последующие N строк содержат по одной записи длиной L, состоящей из строчных латинских букв – надписи на блоках соответствующего типа. Надписи на блоках разных типов не совпадают.

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

Формат выходных данных

В первой строке выходного файла необходимо вывести натуральное число K – минимальное количество блоков, которое нужно использовать для составления новой рекламы. Следующая строка должна содержать K чисел – номера типов блоков, которые нужно для этого использовать, перечисляя их сверху вниз. Типы блоков нумеруются с единицы в порядке их задания во входном файле.

Если ответов несколько, выведите любой из них. Если решения не существует, выведите в выходной файл число –1.

Примеры входных и выходных данных

input.txt - 1

3 4

tiet

oink

ezin

zenit

output.txt - 1

3

1 2 3

input.txt - 2

2 11

sillysample

happysample

sam

output.txt - 2

1

2

input.txt - 3

2 3

baa

aab

bb

output.txt - 3

2

2 2

input.txt - 4

2 3

aaa

bbb

cc

output.txt - 4

-1

Система оценивания

Решения, правильно работающие только для N ≤ 5, будут оцениваться из 50 баллов.

Сдать задачу

Задать вопрос жюри по этой задаче