Welcome to ZOJ
 Problem Sets Information Select Problem Runs Ranklist
ZOJ Problem Set - 4029

Time Limit: 1 Second      Memory Limit: 131072 KB

DreamGrid has $n$ integers $a_1,a_2,\dots,a_n$. DreamGrid also has $m$ queries, and each time he would like to know the value of $$\sum\limits_{1 \le i \le n}\Bigl\lfloor \frac{a_i}{\lceil\log_{p}a_i\rceil}\Bigr\rfloor$$ for a given number $p$, where $\lfloor x \rfloor = \max\{y \in \mathbb{Z} \mid y \le x\}$, $\lceil x \rceil = \min\{y \in \mathbb{Z} \mid y \ge x\}$.

Input

There are multiple test cases. The first line of input is an integer $T$ indicating the number of test cases. For each test case:

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 5 \times 10^5$) -- the number of integers and the number of queries.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($2 \le a_i \le 10^{9}$).

The third line contains $m$ integers $p_1, p_2, \dots, p_m$ ($2 \le p_i \le 10^{9}$).

It is guaranteed that neither the sum of all $n$ nor the sum of all $m$ exceeds $2 \times 10^6$.

Output

For each test case, output an integer $(\sum\limits_{i=1}^{m} i \cdot z_i) \bmod 10^9$, where $z_i$ is the answer for the $i$-th query.

Sample Input

2
3 2
100 1000 10000
100 10
4 5
2323 223 12312 3
1232 324 2 3 5


Sample Output

11366
45619


Author: LIN, Xi
Source: The 15th Zhejiang Provincial Collegiate Programming Contest Sponsored by TuSimple
Submit    Status