Dwendwen的快乐暑假

Time Limit
1s
Memory Limit
262144KB
Judge Program
Standard
Ratio(Solve/Submit)
14.58%(7/48)
Description:

暑假来了,身在华东师范大学的Dwendwen开心地准备回家过暑假了。在玩耍的过程中,突然有个学妹问她一个问题:
给定字符串序列Q<s1,…,sn>,产生一个序列P,其产生方法如下:
1. Q=<s1,…,sn> 
2. Q中每个字符串si将会被其所有前缀所代替,从而产生序列P
例如:
1. Q=<aab,ab>

2. 产生P=<a,aa,aab,a,ab>

共有26个正整数d1,…,d26分别表示着小写字母a,…,z的贡献。
每个字符串si的总贡献值计算方式是si串每个字母贡献值的乘积(mod m)。
现在想要知道对于Q序列中每个字符串si,在P序列中有多少个字符串是其前缀,并且满足字符串总贡献值大于字符串si

Input:

第一行输入一个T(1 <= T <= 8),表示T个测试样例。

对于每个测试样例,第一行给出n(1 <= n <= 5000)和m(1 <= m <= 1e9+7)。

第二行给出26个正整数d1,…,d26(1 <= di <= 1e5)分别表示着小写字母a,…,z的贡献。

接下来给出n行,每行一个字符串。保证字符串中每个字符都是小写,且字符串总长度不超过200000。

Output:

对于每个测试样例,输出共n个结果,分别代表每个字符串si在P中满足条件字符串的数量。注意每行末尾不要输出空格。

Sample Input:
1
2 15
2 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
aab
ab
Sample Output:
3 0

Submit