D. Отображение
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Метро Санкт-Петербурга тестирует новые дисплеи SupLED. Дисплей показывает монохромную скользящую текстовую строку, напечатанную в SupFont. Текст отображается только один раз и не повторяется. Каждый символ SupFont имеет фиксированный размер $$$w \times h$$$ пикселей, где каждый пиксель может быть либо включенным, либо выключенным. Между последовательными символами текста есть столбец выключенных пикселей. Скорость скольжения текста составляет один пиксель за такт.

Основным фактором срока службы является количество переключений: когда пиксель меняет состояние с включенного на выключенное или наоборот. Пиксель выходит из строя после $$$s$$$ переключений. Если состояние пикселя не меняется между двумя тактами, переключений не происходит.

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

Входные данные

Первая строка ввода содержит четыре целых числа $$$n$$$, $$$w$$$, $$$h$$$ и $$$s$$$ — количество символов в SupFont, ширина и высота каждого символа и количество переключений, после которого пиксель выходит из строя ($$$1 \le n \le 94$$$; $$$1 \le w, h \le 30$$$; $$$1 \le s \le 10^6$$$).

Следующие строки содержат описания символов SupFont. Первая строка каждого описания содержит символ ASCII (используются только символы с кодами от 33 до 126 включительно). За символом следует изображение символа с $$$h$$$ строками длиной $$$w$$$, где '#' обозначает включенный пиксель, а '.' обозначает выключенный пиксель. Каждое изображение содержит как минимум один включенный пиксель.

Все описанные символы ASCII различны, но некоторые из них могут иметь одинаковое изображение.

Выходные данные

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

Пример
Входные данные
3 4 5 16
I
.#..
#.#.
.#..
.#..
###.
C
.##.
#..#
#...
#..#
.##.
P
###.
#..#
###.
#...
#...
Выходные данные
ICPC