Monocarp 有 $$$n$$$ 个披萨,第 $$$i$$$ 个披萨由 $$$a_i$$$ 片组成。披萨用大写拉丁字母表示 A 到拉丁字母表中的第 $$$n$$$ 个字母。
Monocarp 还有 $$$m$$$ 好友,他想邀请 正好两个 他们去吃披萨。对于每个朋友,Monocarp 都知道该朋友喜欢哪种披萨。
朋友们到达 Monocarp 家后,对于每个披萨,都会发生以下情况:
- 如果受邀的两个朋友都不喜欢披萨,Monocarp 就会吃掉它;
- 如果两个受邀朋友中的一位恰好喜欢披萨,则该朋友会吃掉它;
- 如果两个朋友都喜欢披萨,他们会尝试分割它。如果它由偶数个切片组成,则它们都吃掉正好一半的切片。但如果披萨由奇数片组成,他们就会开始争吵,试图决定谁要多吃一片——而 Monocarp 不喜欢这样。
对于从 $$$0$$$ 到 $$$\sum a_i$$$ 的每个 $$$k$$$,计算选择的方式数量 正好两个朋友 邀请,这样朋友们就不会吵架,Monocarp 正好吃 $$$k$$$ 片。
输入
第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 20$$$; $$$2 \le m \le 5 \cdot 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 \cdot 10^4$$$) — 披萨的大小。
输出
打印$$$\sum a_i + 1$$$整数,其中第$$$k$$$个整数(从$$$0$$$开始)应该是选择的方式数 正好两个朋友 邀请,这样朋友们就不会吵架,Monocarp 正好吃 $$$k$$$ 片。
示例
输入复制
3 6A AB ABC AB BC C2 3 5
输出复制
4 0 0 1 0 2 0 0 0 0 0
注意
让我们考虑第一个示例中的所有朋友对:
- 如果Monocarp邀请朋友$$$1$$$和$$$2$$$,他们会吃披萨$$$1$$$和$$$2$$$,而他会吃$$$3$$$-rd披萨;
- 如果Monocarp邀请朋友$$$1$$$和$$$3$$$,他们会吃掉所有的披萨;
- 如果Monocarp邀请朋友$$$1$$$和$$$4$$$,他们会吃披萨$$$1$$$和$$$2$$$,他会吃$$$3$$$-rd披萨;
- 如果Monocarp邀请朋友$$$1$$$和$$$5$$$,他们会吃掉所有的披萨;
- 如果Monocarp邀请朋友$$$1$$$和$$$6$$$,他们会吃披萨$$$1$$$和$$$3$$$,而他会吃$$$2$$$-nd披萨;
- 如果Monocarp邀请朋友$$$2$$$和$$$3$$$,他们会因为$$$2$$$-nd披萨而吵架;
- 如果Monocarp邀请朋友$$$2$$$和$$$4$$$,他们会因为$$$2$$$-nd披萨而吵架;
- 如果Monocarp邀请朋友$$$2$$$和$$$5$$$,他们会因为$$$2$$$-nd披萨而吵架;
- 如果Monocarp邀请朋友$$$2$$$和$$$6$$$,他们会吃掉所有的披萨;
- 如果Monocarp邀请朋友$$$3$$$和$$$4$$$,他们会因为$$$2$$$-nd披萨而吵架;
- 如果Monocarp邀请朋友$$$3$$$和$$$5$$$,他们会因为$$$2$$$-nd披萨而吵架;
- 如果Monocarp邀请朋友$$$3$$$和$$$6$$$,他们会因为$$$3$$$-rd披萨而吵架;
- 如果Monocarp邀请朋友$$$4$$$和$$$5$$$,他们会因为$$$2$$$-nd披萨而吵架;
- 如果Monocarp邀请朋友$$$4$$$和$$$6$$$,他们会吃掉所有的披萨;
- 如果Monocarp邀请朋友$$$5$$$和$$$6$$$,他们会因为$$$3$$$-rd披萨而吵架。