题目描述

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

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

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

输入格式

第一行两个数 $k$ 和 $n$ 。

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

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

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

3 7 
010
001
100
abacaba

aac

3 5
010
001
100
bcacb

bacb

子任务序号	分数	$n$	$k$	依赖
$1$	$10$	$\leq 20$	$\leq 26$
$2$	$12$	$\leq 50$	$\leq 5$
$3$	$16$	$\leq 300$	$\leq 5$	$2$
$4$	$17$	$\leq 500$	$\leq 26$	$1\sim 3$
$5$	$10$	$\leq 2\times 10^3$		$1\sim 4$
$6$	$9$	$\leq 10^4$		$1\sim 5$
$7$	$8$	$\leq 10^5$		$1\sim 6$
$8$	$11$	$\leq 5\times 10^5$	$\leq 2$
$9$	$7$	$\leq 5\times 10^5$	$\leq 26$	$1\sim 8$

对于全部数据， $1\leq k\leq 26 ,1\leq n \leq 5\times 10^5$ 。