题目描述

你正在手机上玩一款名为《家乡原野》的游戏。游戏中有一排从左到右排列的 $n$ 个水晶，每个水晶属于 $k$ 种类型之一，用前 $k$ 个小写英文字母表示。因此，这排水晶可以写成一个字符串。

一次操作可以从序列中删除一个水晶。你的目标是通过若干次允许的删除操作，得到字典序最小的字符串。

允许删除的类型由一个 $k\times k$ 的 01 矩阵 $A$ 给出。如果 $A_{ij}=1$，则当类型为 $j$ 的水晶左边紧挨着一个类型为 $i$ 的水晶时，可以删除这个类型为 $j$ 的水晶。操作可以按任意顺序进行。

字典序定义如下：字符串 $x$ 小于字符串 $y$，当且仅当满足以下之一：

1. 存在某个二者都包含的位置 $p$，在 $p$ 之前两个字符串完全相同，且 $x_p<y_p$；
2. $x$ 是 $y$ 的严格前缀。

输入格式

第一行包含两个整数 $k,n$，表示水晶类型数和初始序列长度。

接下来 $k$ 行给出矩阵 $A$，第 $i$ 行包含恰好 $k$ 个字符 0 或 1，第 $j$ 个字符表示 $A_{ij}$。

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

输出格式

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

数据范围

• $1\le k\le 26$；
• $1\le n\le 500000$。

样例

样例 1 输入

3 7
010
001
100
abacaba

样例 1 输出

aac

样例 2 输入

3 5
010
001
100
bcacb

样例 2 输出

bacb

样例说明

两个样例中允许的删除关系为：在 a 后可删 b，在 b 后可删 c，在 c 后可删 a。

第一个样例的一种删除过程为：

abacaba
abacaa
abaca
abac
aac

第二个样例的一种删除过程为：

bcacb
bacb

子任务