题目背景

翻译自 ROI 2021 D1T2。

题目描述

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

在游戏的一步中，可以从序列中移除一个水晶。玩家的目标是通过用允许的删除方式，得到字典序最小的字符串。

允许的删除方式由大小为 $k\times k$ 的表 $A$ 定义，表中的元素只包含 $0$ 和 $1$。如果 $A_{i,j} = 1$，则表示当前面紧邻它的水晶是类型 $i$ 时，允许删除类型 $j$ 的水晶。这些操作可以按任意顺序执行。

字符串 $x$ 在字典序上小于字符串 $y$，需要满足以下条件之一：

• 存在一个位置 $m$，在两个字符串中都存在，且在该位置之前，两个字符串的字符是相同的，但是 $x$ 的第 $m$ 个字符小于 $y$ 的第 $m$ 个字符，
• 字符串 $x$ 是字符串 $y$ 的严格前缀（即从字符串 $y$ 末尾删除一个或多个字符得到）。

举个例子，ccf 的字典序小于 cff，因为 ccf 的第 $2$ 位（c）小于 cff 的第 $2$ 位（f）；而 noi 的字典序小于 noip，因为 noi 是 noip 的严格前缀。

输入格式

第一行给出两个整数 $k$ 和 $n$（$1 \le k \le 26,1 \le n \le 500000$），分别表示水晶的种类数量和初始水晶序列的长度。

接下来的 $k$ 行给出表 $A$，第 $i$ 行包含 $k$ 个字符，都是 $0$ 或 $1$。第 $i$ 行第 $j$ 列的字符为 $A_{ij}$。

最后一行是由 $n$ 个小写英文字母组成的字符串，表示初始水晶序列。保证字符串中只包含前 $k$ 个英文字母（如前七个英文字母分别是 a，b，c，d，e，f，g），第 $i$ 个字母代表第 $i$ 种类型的水晶。

输出格式

输出可以通过操作得到的字典顺序最小的字符串。

3 7
010
001
100
abacaba

aac

3 5
010
001
100
bcacb

bacb

提示

样例解释：

这两个样例的 $A$ 是相同的，它们都只允许这三种类型的删除（下划线的是它的前面一个字符，删除线的是被删除的字符）：$\underline\text{a}\xcancel\text{b},\underline\text{b}\xcancel\text{c},\underline\text{c}\xcancel\text{a}$。

样例 $1$ 中可以这样删除：

样例 $2$ 中可以这样删除：

• $\text{bcacb}$
• \underline\text{b}\xcancel\text{c}\text{acb}
• $\text{bacb}$

数据范围：

对于 $100\%$ 的数据，$n\le500000$，$k\le26$。