Problem 4159: Digit Sum

Task

Little Digit is, for whatever reason, interested in the sum of digits of numbers. For any non-negative integer $x$ , let $DigitSum(x)$ the sum of the digits of $x$ . For example

\begin{align*} DigitSum(123) &= 1 + 2 + 3 = 6,\\ DigitSum(998 \ 877) &= 9 + 9 + 8 + 8 + 7 + 7 = 48,\\ DigitSum(0) &= 0. \end{align*}

Her friend, Little Square, gave her an array $A_1, \ldots, A_N$ of $N$ non-negative integers, as well as another array $X_1, \ldots, X_Q$ of $Q$ non-negative integers. For every $i = 1, \ldots, Q$ , help her find the sum

DigitSum(X_i + A_1) + \cdots + DigitSum(X_i + A_N).

Input data

The first line contains $N$ and $Q$ . The next $N + Q$ lines contain the numbers $A_1, \ldots, A_N, X_1, \ldots, X_Q$ , in that order, each on one line.

Output data

Output $Q$ lines. Line $i$ of the output should contain the sum

DigitSum(X_i + A_1) + \cdots + DigitSum(X_i + A_N).

Constraints and clarifications

$1 \leq N, Q \leq 5 \ 000$ ;
$1 \leq A_i, X_i \leq 10^{2 \ 000}$ .

#	Points	Constraints
1	19	$X_i, A_i \leq 10^9$
2	18	$X_i, A_i$ consist only of digits $0, 1, 2, 3, 4$
3	15	$N, Q \leq 300$ and $X_i, A_i \leq 10^{300}$
4	24	$N, Q \leq 1 \ 000$
5	24	No other restrictions

Example

stdin

stdout

39
41
42

Explanation

The input is

\begin{align*} A_1 &= 10,\\ A_2 &= 8,\\ A_3 &= 72,\\ A_4 &= 13,\\ A_5 &= 26 \end{align*}

and

\begin{align*} X_1 &= 18,\\ X_2 &= 31,\\ X_3 &= 15. \end{align*}

We must compute 3 sums.

The first sum is
$DigitSum(X_1 + A_1) + \cdots + DigitSum(X_1 + A_5) \\ = DigitSum(18 + 10) + DigitSum(18 + 8) + DigitSum(18 + 72) + DigitSum(18 + 13) + DigitSum(18 + 26) \\ = DigitSum(28) + DigitSum(26) + DigitSum(90) + DigitSum(31) + DigitSum(44) \\ = 2 + 8 + 2 + 6 + 9 + 0 + 3 + 1 + 4 + 4 = 39$

The second sum is

$DigitSum(X_2 + A_1) + \cdots + DigitSum(X_2 + A_5) \\ = DigitSum(31 + 10) + DigitSum(31 + 8) + DigitSum(31 + 72) + DigitSum(31 + 13) + DigitSum(31 + 26) \\ = DigitSum(41) + DigitSum(39) + DigitSum(103) + DigitSum(44) + DigitSum(57) \\ = 4+ 1 + 3+ 9 + 1+ 0 +3 + 4+ 4 + 5+ 7= 41$

The third sum is

$DigitSum(X_3 + A_1) + \cdots + DigitSum(X_3 + A_5) \\ = DigitSum(15 + 10) + DigitSum(15 + 8) + DigitSum(15 + 72) + DigitSum(15 + 13) + DigitSum(15 + 26) \\ = DigitSum(25) + DigitSum(23) + DigitSum(87) + DigitSum(28) + DigitSum(41)\\ = 2+ 5 + 2+ 3 + 8+ 7 + 2+ 8 + 4+ 1=42.$

Digit Sum