题目描述

译自 ROI 2021 Day1 T2. Родные просторы

你正在玩一款叫做《复兴家园》的手机游戏，游戏中管家奥斯塔普帮助地主修复祖宅。游戏的玩法如下：

给定一列长度为 $n$ 的水晶，从左到右排列。每个水晶属于 $k$ 种类型之一，用前 $k$ 个英文字母表示。因此，水晶序列可以表示为一个由英文字母组成的字符串。

每次游戏操作可以删除序列中的一个水晶。玩家的目标是通过合法的删除操作，得到字典序最小的字符串。

合法的删除操作由一个大小为 $k \times k$ 的矩阵 $A$ 给出，矩阵中的元素为 $0$ 或 $1$。如果 $A_{ij} = 1$，则可以删除类型为 $j$ 的水晶，前提是它左边紧挨着一个类型为 $i$ 的水晶。这些操作可以按任意顺序执行。

输入格式

第一行包含两个整数 $k, n$ $(1 \le k \le 26, 1 \le n \le 5\cdot 10^5)$，分别表示水晶的种类数和初始序列的长度。

接下来的 $k$ 行中，每行包含 $k$ 个字符 $0$ 或 $1$，表示矩阵 $A$。第 $i$ 行第 $j$ 列的字符表示 $A_{ij}$。

最后一行包含一个长度为 $n$ 的字符串，表示初始的水晶序列。保证字符串中只包含前 $k$ 个英文字母。

输出格式

输出通过合法的删除操作可以得到的字典序最小的字符串。

样例 1

输入

3 7
010
001
100
abacaba

输出

aac

在样例中，合法的删除操作如下（删除的字符用删除线表示，前一个字符用下划线表示）：

• $\underline{a}b$ → 可以删除 $b$（$A_{ab} = 1$）
• $\underline{b}c$ → 可以删除 $c$（$A_{bc} = 1$）
• $\underline{c}a$ → 可以删除 $a$（$A_{ca} = 1$）

第一个样例中的可能删除顺序：

abacaba
abacaba
abacaa
abacaa
abaca
abaca
abac
abac
aac

样例 2

输入

3 5
010
001
100
bcacb

输出

bacb

第二个样例中的可能删除顺序：

bcacb
bcacb
bacb

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。

子任务	分值	$n$ 的限制	$k$ 的限制	子任务依赖
1	$10$	$n \le 20$	$k \le 26$	0
2	$12$	$n \le 50$	$k \le 5$
3	$16$	$n \le 300$		0, 2
4	$17$	$n \le 500$	$k \le 26$	0, 1~3
5	$10$	$n \le 2000$		0, 1~4
6	$9$	$n \le 10^4$		0, 1~5
7	$8$	$n \le 10^5$		0, 1~6
8	$11$	$n \le 5\cdot 10^5$	$k \le 2$
9	$7$		$k \le 26$	0, 1~8