圣彼得堡 Supway 地铁正在测试新的 SupLED 跑马灯显示屏。该显示屏显示一行用 SupFont 字体印刷的单色滚动文本。文本仅显示一次，且不循环。每个 SupFont 字符具有固定的 $w \times h$ 像素大小，其中每个像素要么亮起，要么熄灭。在文本的相邻字符之间有一列熄灭的像素。文本的滚动速度为每 tick 一个像素。

主要的使用寿命因素是开关次数：即像素从亮起变为熄灭，或反之。一个像素在经过 $s$ 次开关后就会损坏。如果一个像素的状态在两个 tick 之间没有发生变化，则不发生开关。

服务团队需要估算使任意一个像素损坏的最短文本。在文本显示之前，所有像素都是熄灭的。

输入格式

输入的第一行包含四个整数 $n, w, h$ 和 $s$ —— SupFont 中字符的数量、每个字符的宽度和高度，以及导致像素损坏所需的开关次数（$1 \le n \le 94$；$1 \le w, h \le 30$；$1 \le s \le 10^6$）。

接下来的行包含 SupFont 字符的描述。每个描述的第一行包含一个 ASCII 字符（仅使用 ASCII 码在 33 到 126 之间的字符，包含首尾）。接着是该字符的图像，共 $h$ 行，每行长度为 $w$，其中 '#' 表示亮起的像素，'.' 表示熄灭的像素。每个图像至少包含一个亮起的像素。

所有描述的 ASCII 字符都是两两不同的，但它们之中有一些可能具有相同的图像。

输出格式

输出单行，包含最多 $s$ 个字符：在显示屏上显示时，能使某个像素至少切换 $s$ 次的最短文本。如果存在多个解决方案，输出其中任意一个。

样例

输入样例 1

3 4 5 16
I
.#..
#.#.
.#..
.#..
###.
C
.##.
#..#
#...
#..#
.##.
P
###.
#..#
###.
#...
#...

输出样例 1

ICPC