题目描述

译自 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$ 个英文字母。

输出格式

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

3 7
010
001
100
abacaba

aac

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

• ab
• bc
• ca

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

1. abacaba
2. abacaba
3. abacaa
4. abacaa
5. abaca
6. abaca
7. abac
8. abac
9. aac

3 5
010
001
100
bcacb

bacb

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

1. bcacb
2. bcacb
3. bacb

数据范围与提示

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