5623 - 提高:重叠区间

通过次数

10

提交次数

21

Time Limit : 1 秒
Memory Limit : 256 MB

一个长度为M的A型01串,另外有k个长度为M的B型01串,请问需要多少B型字符串,叠加后能把A型中的1挡住(用B型中的1去挡住)

Input

第一行输入两个正整数n,m,代表A型的数量和长度; 接下来的n行,每行输入一个长度为m的01串,代表A型。 接下来一行输入一个正整数k,代表B型的数量。 接下来的k行,每行输入一个长度为m的01串,代表B型01串的情况。1≤m≤20,1≤n≤10^4,1≤k≤10

Output

输出n行,每行输出挡住时所需的最小B型01串数量。特殊的,如果该无法挡住,请输出-1。

Examples

Input

3 4
1000
0101
1011
2
1001
0011

Output

1
-1
2