The 2019 ICPC China Nanchang National Invitational and International Silk-Road Programming Contest J

传送门

yah has nnn strings < s_1, \cdots ,s_n >, and he generates a sequence PPP by two steps:

1. P=P = < s_1, \cdots ,s_n >P=
2. Replace each sis_isi​ with all prefixes of itself.

An example is:

1. the nnn strings are < aab,ab >
2. first, P=P =< aab,ab >P=
3. then, P=P =< a,aa,aab,a,ab >P=

There are 262626 positive integers d1,⋯,d26d_1, \cdots ,d_{26}d1​,⋯,d26​ that denote the difficulty to identify lowercase English letter a,b,⋯,za,b, \cdots ,za,b,⋯,z for yah.

The difficulty to identify a string strstrstr is (∏i=1∣str∣dstri)(\displaystyle\prod_{i=1}^{|str|} d_{str_i}) (i=1∏∣str∣​dstri​​) mod  mmm

Now, yah wants to calculate: for each string si(i=1,⋯,n)s_i (i = 1, \cdots ,n)si​(i=1,⋯,n), the number of strings in PPP that is prefix of sis_isi​ and more difficult than sis_isi​.

Input

The first line contains two integers n,m(1≤n≤105,1≤m≤2×105)n,m(1 \le n \le 10^5,1 \le m \le 2 \times 10^5)n,m(1≤n≤105,1≤m≤2×105).

The second line contains 262626 positive d1,⋯,d26d_1, \cdots ,d_{26}d1​,⋯,d26​,0≤di≤1050 \le d_i \le 10^50≤di​≤105.

The following nnn lines, each line contains a string, the ithi_{th}ith​ lines contains sis_isi​, the sum of length of all strings is not great than 2×1052 \times 10^52×105.

Output

The only line contains nnn integers, the ithi_{th}ith​ integer denoting the number of strings in PPP that is prefix of sis_isi​ but more difficult to identify for yah.

Hint

P=P =< a,aa,aab,a,ab >P=, a,aa,aa,aa,aa,aa,a are prefixes of aabaabaab with greater difculty.

输出时每行末尾的多余空格，不影响答案正确性

样例输入

2 15
2 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
aab
ab 

样例输出

3 0     

#include
using namespace std;
int n,m,cnt=0;
int d[30];
int trie[100100][30];
int color[10010];
int k = 1;
string s[100100];
vector  v;
mapmp,cs;
typedef long long ll;
void insert(string w){int len = w.length();int p = 0;for(int i=0; i>s[i];ll ssw=1;string ss;for(int j=0;j

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！