点菜

题目描述

奶龙在点菜, 它指着菜单 $D$, 说了一句话 $S$. 其中 $D$ 是包含一系列的字符串的字典, 每个字符串是一道菜名. $S$ 是一个字符串.

老板需要根据奶龙说的话确认他点的菜, 由于大家点菜时都喜欢用简称, 如点 "鸡蛋肠粉" 时, 只需要说 "鸡蛋肠", 点 "百事可乐", 只需要说 "百事", 所以只要说出 $D$ 中某道菜名的前缀, 就可以认为是点了一道菜。具体地, 老板需要将字符串 $S$ 划分为若干段，使得每一段是 $D$ 中某个字符串的前缀.

对于 $S$ 的每个位置 $i$, 有一个价格 $cost_i$. 如果一道菜以 $i$ 结尾则需要支付 $cost_i$ 的价格. ($cost$ 可能为负值)

奶龙想知道, 他说出 $S$ 的前 $i$ 个字符后, 他需要支付的最少价格是多少. 请你对于所有 $1 \leq i \leq n$, 求出 $S$ 的长度为 $i$ 的前缀在经过老板划分后, 奶龙支付的最小代价。

输入格式

第一行包含两个整数 $n$ 和 $m$，表示字符串 $S$ 的长度和菜单 $D$ 中菜名的数量。

第二行是长度为 $n$ 的字符串 $S$. 第三行包含 $n$ 个整数，表示每个位置的 $cost_i$. 接下来 $m$ 行, 每行一个字符串，每个字符串为菜单中的菜名.

输出格式

输出 $n$ 行，共计 $n$ 个整数，表示奶龙说出 $S$ 的前 $i$ 位后需要支付的最少价格。 如果老板不存在方法将其划分为若干菜名的前缀，则输出 noway.

样例 #1

样例输入 #1

5 3
abcde
1 -1 -2 -3 4
abc
de
abcde

样例输出 #1

1
-1
-2
-5
2

样例 #2

样例输入 #2

5 4
abaea
1 -1 100 -3 4
ab
ac
c
b

样例输出 #2

1
-1
99
noway
noway

数据范围

对 $100\%$ 的数据:

• 字符串 $S$ 的长度 $n$ 满足 $1 \leq n \leq 10^6$。
• 菜单中的菜名数量 $m$ 满足 $1 \leq m \leq 100000$，每个菜名长度不超过 $n$，总长度 $L$ 不超过 $10^6$。
• $-1000 \leq cost_i \leq 1000$。
• 菜单 $D$ 中的所有菜名均为非空字符串。
• $S$ 和 $D$ 的字符集均为小写英文字母。

Subtask 1 10pts

• $n \leq 5000$
• $m \leq 500$
• 菜单的总长度 $L \leq 5000$

Subtask 2 20pts

• 保证菜单中每个菜名长度不超过 $20$

Subtask 3 30pts

• $n \leq 50000$
• $m \leq 5000$
• 菜单的总长度 $L \leq 50000$

Subtask 4 40 pts

• 无额外保证