F. 朋友与披萨

每个测试点的时间限制：$8$ 秒
每个测试点的内存限制：$512$ 兆字节

Monocarp 有 $n$ 个披萨，第 $i$ 个披萨有 $a_i$ 片。披萨用大写英文字母 $A$ 到第 $n$ 个字母表示。

Monocarp 还有 $m$ 个朋友，他想邀请恰好其中两位来吃披萨。对于每位朋友，Monocarp 知道他喜欢哪些披萨。

朋友们到达 Monocarp 家后，对于每个披萨，会发生以下情况：

• 如果两个被邀请的朋友都不喜欢这个披萨，Monocarp 会吃掉它；
• 如果恰好其中一个朋友喜欢这个披萨，那么那位朋友会吃掉它；
• 如果两个朋友都喜欢这个披萨，他们会尝试平分它。如果披萨的片数是偶数，他们每人恰好吃一半；但如果披萨的片数是奇数，他们会开始争吵，试图决定谁多吃一片——而 Monocarp 不喜欢这样。

对于每个 $k$ 从 $0$ 到 $\sum a_i$，请计算恰好选择两位朋友邀请的方案数，使得朋友不争吵，并且 Monocarp 恰好吃掉 $k$ 片。

输入
第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 20$；$2 \le m \le 5 \times 10^5$）——披萨的数量和朋友的数量。

第二行包含 $m$ 个字符串 $s_1, s_2, \dots, s_m$（$1 \le |s_i| \le n$），其中 $s_i$ 是由从 $A$ 到第 $n$ 个字母的不同字符组成的字符串，表示第 $i$ 个朋友喜欢哪些披萨。每个字符串 $s_i$ 中的字符按字典序（字母顺序）排序。

第三行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 2 \times 10^4$）——每个披萨的片数。

输出
输出 $\sum a_i + 1$ 个整数，其中第 $k$ 个整数（从 $0$ 开始计数）应该是恰好选择两位朋友邀请且朋友不争吵、Monocarp 恰好吃掉 $k$ 片的方案数。

示例
输入

3 6
A AB ABC AB BC C
2 3 5

输出

4 0 0 1 0 2 0 0 0 0 0 

注意
考虑第一个示例中所有朋友对：

• 邀请朋友 $1$ 和 $2$：他们会吃掉披萨 $1$ 和 $2$，Monocarp 吃掉披萨 $3$；
• 邀请朋友 $1$ 和 $3$：他们会吃掉所有披萨；
• 邀请朋友 $1$ 和 $4$：他们会吃掉披萨 $1$ 和 $2$，Monocarp 吃掉披萨 $3$；
• 邀请朋友 $1$ 和 $5$：他们会吃掉所有披萨；
• 邀请朋友 $1$ 和 $6$：他们会吃掉披萨 $1$ 和 $3$，Monocarp 吃掉披萨 $2$；
• 邀请朋友 $2$ 和 $3$：会因披萨 $2$ 争吵；
• 邀请朋友 $2$ 和 $4$：会因披萨 $2$ 争吵；
• 邀请朋友 $2$ 和 $5$：会因披萨 $2$ 争吵；
• 邀请朋友 $2$ 和 $6$：他们会吃掉所有披萨；
• 邀请朋友 $3$ 和 $4$：会因披萨 $2$ 争吵；
• 邀请朋友 $3$ 和 $5$：会因披萨 $2$ 争吵；
• 邀请朋友 $3$ 和 $6$：会因披萨 $3$ 争吵；
• 邀请朋友 $4$ 和 $5$：会因披萨 $2$ 争吵；
• 邀请朋友 $4$ 和 $6$：他们会吃掉所有披萨；
• 邀请朋友 $5$ 和 $6$：会因披萨 $3$ 争吵。