CF1490G.Old Floppy Drive

Polycarp was dismantling his attic and found an old floppy drive on it. A round disc was inserted into the drive with $n$ integers written on it.

Polycarp wrote the numbers from the disk into the $a$ array. It turned out that the drive works according to the following algorithm:

• the drive takes one positive number $x$ as input and puts a pointer to the first element of the $a$ array;
• after that, the drive starts rotating the disk, every second moving the pointer to the next element, counting the sum of all the elements that have been under the pointer. Since the disk is round, in the $a$ array, the last element is again followed by the first one;
• as soon as the sum is at least $x$, the drive will shut down.

Polycarp wants to learn more about the operation of the drive, but he has absolutely no free time. So he asked you $m$ questions. To answer the $i$-th of them, you need to find how many seconds the drive will work if you give it $x_i$ as input. Please note that in some cases the drive can work infinitely.

For example, if $n=3, m=3$, $a=[1, -3, 4]$ and $x=[1, 5, 2]$, then the answers to the questions are as follows:

• the answer to the first query is $0$ because the drive initially points to the first item and the initial sum is $1$.
• the answer to the second query is $6$, the drive will spin the disk completely twice and the amount becomes $1+(-3)+4+1+(-3)+4+1=5$.
• the answer to the third query is $2$, the amount is $1+(-3)+4=2$.

波利卡普在整理阁楼时，发现了一个旧的软盘驱动器。一个圆形的磁盘被插入驱动器中，其上写有 $n$ 个整数。

波利卡普将磁盘上的数字依次记录到数组 $a$ 中。结果发现，该驱动器按照如下算法工作：

• 驱动器接收一个正整数 $x$ 作为输入，并将指针初始指向数组 $a$ 的第一个元素；
• 接着，驱动器开始旋转磁盘，每秒将指针移动至下一个元素，并累加所有曾被指针指向过的元素之和。由于磁盘是环形的，因此在数组 $a$ 中，最后一个元素之后紧接着是第一个元素；
• 一旦累加和至少达到 $x$，驱动器即刻停止运行。

波利卡普想进一步了解该驱动器的工作原理，但他完全抽不出空闲时间。因此，他向你提出了 $m$ 个问题。对于第 $i$ 个问题，你需要计算：当输入为 $x_i$ 时，驱动器将持续运行多少秒。请注意，在某些情况下，驱动器可能永远无法停止（即无限运行）。

例如，若 $n=3, m=3$，$a=[1, -3, 4]$，且 $x=[1, 5, 2]$，则各查询的答案如下：

• 第一个查询的答案为 $0$，因为驱动器初始时指针已指向第一个元素，此时初始累加和即为 $1$；
• 第二个查询的答案为 $6$，驱动器将完整旋转磁盘两圈，累加和变为 $1+(-3)+4+1+(-3)+4+1=5$；
• 第三个查询的答案为 $2$，累加和为 $1+(-3)+4=2$。

The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Then $t$ test cases follow.

The first line of each test case consists of two positive integers $n$, $m$ ($1 \le n, m \le 2 \cdot 10^5$) — the number of numbers on the disk and the number of asked questions.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-10^9 \le a_i \le 10^9$).

The third line of each test case contains $m$ positive integers $x_1, x_2, \ldots, x_m$ ($1 \le x \le 10^9$).

It is guaranteed that the sums of $n$ and $m$ over all test cases do not exceed $2 \cdot 10^5$.

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 测试用例的数量。随后是 $t$ 个测试用例。

每个测试用例的第一行包含两个正整数 $n$、$m$（$1 \le n, m \le 2 \cdot 10^5$）—— 分别表示磁盘上数字的个数以及询问的次数。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$-10^9 \le a_i \le 10^9$）。

每个测试用例的第三行包含 $m$ 个正整数 $x_1, x_2, \ldots, x_m$（$1 \le x \le 10^9$）。

保证所有测试用例中 $n$ 的总和与 $m$ 的总和均不超过 $2 \cdot 10^5$。

Print $m$ numbers on a separate line for each test case. The $i$-th number is:

• $-1$ if the drive will run infinitely;
• the number of seconds the drive will run, otherwise.

每个测试用例输出 $m$ 个数字，每个数字占一行。其中第 $i$ 个数字为：

• 若驱动器将无限运行，则为 $-1$；
• 否则为驱动器运行的秒数。