We are given a set of positive integers.
For a given sequence of digits , we would like to know
how many times it occurs, as a fragment (i.e., a contiguous part),
in the numbers from the set .
Note that a sequence may occur as a fragment of a given
multiple times - then we are interested in all its occurrences.
Input
The first line of the standard input contains two integers and
(, )
representing the number of lines containing a description of the set
and the number of sequences of digits denoting the queries.
Each of the following lines contains two integers and
.
These numbers satisfy the following inequalities:
and represent the following set:
Each of the following lines contains a sequence of digits
consisting of at least 1 and at most 19 digits .
Output
Your program should write lines to the standard output.
The -th of these lines should contain a single integer:
the total number of occurrences of in all numbers from the
set , including multiple occurrences in respective elements of .
Example
For the input data:
1 3
2220 2223
222
0
07
the correct result is:
5
1
0
Task author: Jakub Radoszewski.
Kontakt
W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem szkopul@fri.edu.pl.
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, odwiedź nasze serwery na Discordzie. Są one moderowane przez społeczność, ale członkowie zespołu wsparcia również aktywnie się tam udzielają.