题目描述

定义小写字母的编号为 $\operatorname{ord}(a)=0,\ldots,\operatorname{ord}(z)=25$。

若密钥串 $t$ 的长度整除明文串 $s$ 的长度，则使用循环维吉尼亚密码加密后：

$$e_i=\operatorname{chr}\left((\operatorname{ord}(s_i)+\operatorname{ord}(t_{i\bmod |t|}))\bmod26\right).$$

给定 $K$ 个密钥串和 $N$ 个待加密字符串。对每个字符串 $s_i$，找出能产生字典序最小密文的密钥编号。若多个密钥产生相同的最小密文，输出编号最小者；若不存在长度合法的密钥，输出 $-1$。

输入格式

第一行包含两个整数 $N,K$。

接下来 $K$ 行依次给出密钥串 $t_1,t_2,\ldots,t_K$。

再接下来 $N$ 行依次给出待加密字符串。

输出格式

输出 $N$ 行。第 $i$ 行表示第 $i$ 个待加密字符串的答案。密钥编号从 1 开始。

数据范围

• $1\le N,K\le2\times10^5$；
• 所有密钥串和待加密字符串的长度总和不超过 $4\times10^5$；
• 所有字符均为小写英文字母。

子任务

子任务	分值	限制
1	0	样例
2	20	字符总长度乘 $K$ 不超过 $10^6$
3	50	每个密钥长度都整除每个明文长度
4	30	无额外限制

样例

输入1
3 6
are
mere
ana
oare
cinestie
nimeni
anaana
plebi
nusestie

输出1
3
-1
4