Question
Glow Quest
Mira gathers N binary sequences, each assigned a unique glow value. She receives Q tasks, each providing a binary string P. For each task, compute the total glow of sequences that begin with P. Return the sum modulo 109 + 7.
Input
The first line contains N, number of strings and Q, the number of Queries.
The next N lines contain string P and its beauty value denoted by p.
The next Q lines contain string S.
Constraints:
1 ≤ N, Q ≤ 105
1 ≤ |P|, |S| ≤ 10
1 ≤ p ≤ 1012
The next N lines contain string P and its beauty value denoted by p.
The next Q lines contain string S.
Constraints:
1 ≤ N, Q ≤ 105
1 ≤ |P|, |S| ≤ 10
1 ≤ p ≤ 1012
Output
For each query print the sum of beauty values of all those strings of which string S is a prefix.
Example
Sample Input
5 4
101 5
000 3
001 5
010 1
111 9
00
011
1
0
Sample Output
8
0
14
9
Explanation
Query 1: For S = "00": Codes "000" and "001" start with "00", so sum = 3 + 5 = 8.
Query 2: For S = "011" No codes have starting prefix with "011" hence the sum is 0.
5 4
101 5
000 3
001 5
010 1
111 9
00
011
1
0
Sample Output
8
0
14
9
Explanation
Query 1: For S = "00": Codes "000" and "001" start with "00", so sum = 3 + 5 = 8.
Query 2: For S = "011" No codes have starting prefix with "011" hence the sum is 0.