Question
Prefix Beauty Sum
In a digital world filled with binary strings, Aarav came across N unique strings, each adorned with a special beauty value. Fascinated by these strings, he decided to conduct some queries to explore their relationships.
For each query, Aarav would provide a binary string S, and his task was to discover the total beauty value of all strings that had S as a prefix. Given that the sum could grow quite large, he needed to present the results modulo 109 + 7. Can you help Aarav calculate the beauty value for each of his queries?
Input
The first line contains N, number of strings and Q, the number of Queries.
The next N lines contain string A and its beauty value denoted by p.
The next Q lines contain string S.
Constraints:
1 ≤ N, Q ≤ 105
1 ≤ |A|, |S| ≤ 10
1 ≤ p ≤ 1012
The next N lines contain string A and its beauty value denoted by p.
The next Q lines contain string S.
Constraints:
1 ≤ N, Q ≤ 105
1 ≤ |A|, |S| ≤ 10
1 ≤ p ≤ 1012
Output
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
1
0
011
Sample Output
8
14
9
0
5 4
101 5
000 3
001 5
010 1
111 9
00
1
0
011
Sample Output
8
14
9
0