## 描述

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

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}$.

### 输入

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$.

### 输出

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.

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

11366
45619