删字母

1s|1024Mb

现有一个长度为$n$ ,字符集为前$k$个小写字母的字符串。

给你一个$k \times k$ 的$01$矩阵$A$，如果$A_{i,j} =1$ ，意味着出现了相邻 $i$ 字母和 $j$ 字母，且$i$字母在前面,我们可以删除$j$字母。你可以以任何次数任何顺序进行删除，当然也可以不删。

现在问你，进行若干删除操作之后，能得到最小字典序的字符串是什么。

字典序就是从首位开始，一位一位比较，如果哪一位更小或者哪一位为空就结束。

输入格式

第一行两个数$k$和$n$ 。$(1\leq k\leq 26 ,1\leq n \leq 500000)$。

接下来一个$k \times k$ 的01矩阵。

第$k+2$行一个长度为$n$的字符串。

输出格式

能得到最小字典序的字符串。

样例输入 1

3 7 
010
001
100
abacaba

样例输出 1

aac

样例输入 2

3 5
010
001
100
bcacb

样例输出 2

bacb

下发数据文件 http://bzoj.org/file/2/erase.zip

样例解释

子任务