你现在有 $m$ 种元素，第一种元素的名称为 \t{a}，第二种为 \t{b}，以此类推。你将使用这些元素来打怪。

具体的，你有一个长度为 $n$ 的元素使用序列，你会依次使用这些元素攻击怪物。假设当前元素种类为 $x$，如果怪物身上没有挂上元素，那么将会给怪物挂上元素 $x$；如果怪物身上已经有某种元素 $y$，那么两种元素会发生反应，产生 $a_{y,x}$ 的伤害，并且反应之后怪物身上只剩下元素 $x$，同类元素间也会进行反应。

但是现在某些种类的元素可能有了惰性，即这些元素攻击怪物时不会产生任何反应，也不会挂在怪物身上，会被直接忽略掉。

但你并不知道哪些种类元素有惰性，所以你想知道对于每种元素是否有惰性的 $2^m$ 种情况，分别求出这时候元素序列造成的伤害之和。

Input

第一行输入两个整数 $m,n$（$1\le n\le 10^5,1\le m\le 17$）。

接下来 $m$ 行每行 $m$ 个整数，其中第 $i$ 行第 $j$ 个数表示第 $i$ 种元素在前，第 $j$ 种元素在后时的反应伤害 $a_{i,j}$（$0\le a_{i,j}\le 10^8$）。

接下来一行长度为 $n$ 的字符串，表示给定的元素序列。保证字符串中只出现前 $m$ 个小写英文字母。

Output

输出一行 $2^m$ 个整数，其中第 $i$ 个数表示，将所有元素惰性视为 $1$，非惰性设为 $0$，按照元素种类编号从小到大在二进制位从低到高排列得到的二进制数为 $i-1$ 时元素序列造成的伤害之和。

3 4
1 2 3
4 5 6
7 8 9
abca

15 6 10 0 6 0 1 0

3 10
1 2 3
4 5 6
7 8 9
acbabccbac

47 42 32 27 17 10 2 0