What Does the Lottery Ticket Pay?

In a lottery sale, let's assume that N lottery tickets have been offered, each of which is a natural number ~X_i~ consisting of exactly K decimal digits (lottery tickets are allowed to start with the digit 0). A lucky number Y is drawn. Based on this number, each lottery ticket wins a monetary amount as follows: if the last M digits of lottery ticket ~X_i~ are the same as the last (ending) M digits of the lucky number Y, then the holder of the lottery ticket wins ~2^M-1~ euros.

For example, if K = 6, ~X_i~ = 391742, and Y = 421742, then lottery ticket ~X_i~ has M = 4 common ending digits with the lucky number Y (i.e., both end in 1742), and its holder wins ~2^4-1 =~ 15 euros.

Given the lottery tickets that have been offered and the lucky number, we are asked how many lottery tickets win a non-zero amount (i.e., how many have one or more common ending digits with the lucky number) and what is the total amount won by all lottery tickets. Since the total amount can be a very large number, we are asked to calculate the remainder of the integer division (modulo) of this with the number ~10^9 + 7~.

Problem

Develop a program in one of the IOI languages (Pascal, C, C++, Java) that reads the offered lottery tickets and a series of alternative lucky numbers, and for each alternative lucky number, prints how many lottery tickets win and what is the total amount won.

Input Files:

The input file named lottery.in is a text file with the following structure. The first line contains three integers K, N, and Q, separated in pairs by a single space: K is the number of decimal digits of the lottery tickets, N is the number of lottery tickets offered, and Q is the number of alternative lucky numbers. Each of the next N lines will contain an integer ~X_i~ with exactly K digits, representing a lottery ticket that has been offered. Each of the next Q lines will contain an integer ~Y_i~ with exactly K digits, representing an alternative lucky number.

Output Files:

The output file named lottery.out is a text file with the following structure. It has exactly Q lines. Each of these corresponds in order to an alternative lucky number ~Y_i~ and contains two integers ~C_i~ and ~S_i~ separated by a single space: ~C_i~ is the number of winning lottery tickets, and ~S_i~ is the remainder of the integer division (modulo) of the total amount won by all lottery tickets with the number ~10^9 + 7~.

Examples of Input - Output Files:

1st

STDIN (lottery.in)

6 1 1
391742
421742

STDOUT (lottery.out)

1 15

2nd

STDIN (lottery.in)

4 6 3
3581
2619
4904
8859
3919
4964
4904
8933
3419

STDOUT (lottery.out)

2 16
0 0
3 7

Explanation: There are six lottery tickets (3581, 2619, 4904, 8859, 3919, 4964) and three alternative lucky numbers (4904, 8933, 3419). If the first one (4904) is drawn, then lottery ticket 4904 (which coincides with the lucky number) wins 15 euros, and 4964 wins 1 euro. If the second one (8933) is drawn, then no lottery ticket wins. If the third one (3419) is drawn, then lottery tickets 2619 and 3919 each win 3 euros, and 8859 wins 1 euro.

Constraints:

• For test cases worth 20%, of the total points, it will be:
  1 ~\le~ Κ ~\le~ 9, 1 ~\le~ Ν ~\le~ 1000, 1 ~\le~ Q ~\le~ 1000, 0 ~\le~ ~S_i~ ~\le~ 109
• For test cases worth 40%, of the total points, it will be:
  1 ~\le~ Κ ~\le~ 30, 1 ~\le~ Ν ~\le~ 1000, 1 ~\le~ Q ~\le~ 1000, 0 ~\le~ ~S_i~ ~\le~ 109
• For test cases worth 100%, of the total points, it will be:
  1 ~\le~ Κ ~\le~ 100, 1 ~\le~ Ν ~\le~ 1.000.000, 1 ~\le~ Q ~\le~ 1.000.000
  (N+Q)~\cdot~K ~\le~ 1.000.000

Attention! Be sure to read the input and print the output efficiently, especially if you are programming in C++ or Java.

Formatting: In the output, each line terminates with a newline character.
Maximum execution time: 1 sec.
Maximum available memory: 128 MB.
Headers in the source code: At the beginning of your source code, you should use the following headers

(* USER: username
LANG: PASCAL
TASK: lottery *)

for PASCAL coders

/* USER: username
LANG: C
TASK: lottery */

for C coders

/* USER: username
LANG: C++
TASK: lottery */

for C++ coders

/* USER: username
LANG: Java
TASK: lottery */

for Java coders

# USER: username
# LANG: Python
# TASK: lottery

for Python coders