你现在有 $m$ 种元素。第一种元素的名称是 a，第二种是 b，以此类推。 你将使用这些元素来攻击怪物。

具体来说，你有一个长度为 $n$ 的元素使用序列，并将按顺序使用这些元素攻击怪物。假设当前使用的元素类型为 $x$，如果怪物身上没有附着元素，则元素 $x$ 会附着在怪物身上。如果怪物身上已经附着了某种元素 $y$，则这两个元素会发生反应，造成 $a_{y,x}$ 的伤害。反应结束后，只有元素 $x$ 会留在怪物身上，且相同类型的元素之间也会发生反应。

然而，现在某些类型的元素可能已经变得惰性，这意味着当这些元素被用于攻击时，它们不会与怪物发生反应或附着在怪物身上，而是会被直接忽略。

由于你不知道哪些类型的元素变得惰性，你希望对于每一种元素是否惰性的 $2^m$ 种可能情况，计算出该元素序列造成的总伤害。

输入格式

第一行包含两个整数 $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$ 个小写英文字母。

输出格式

输出一行 $2^m$ 个整数，其中第 $i$ 个数表示当所有元素被视为惰性（记为 1）和非惰性（记为 0）时，元素序列造成的总伤害。其中，将元素类型按升序排列，从最低有效位到最高有效位组成的二进制数即为 $i - 1$。

样例

样例输入 1

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

样例输出 1

15 6 10 0 6 0 1 0

样例输入 2

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

样例输出 2

47 42 32 27 17 10 2 0