CF1490G Old Floppy Drive

Polycarp 在整理他的阁楼时，发现了一个旧的软盘驱动器。驱动器里插着一张圆盘，上面写有 $n$ 个整数。 Polycarp 将盘上的数字记录到了数组 $a$ 中。驱动器的工作方式如下： - 驱动器接收一个正整数 $x$ 作为输入，并将指针指向数组 $a$ 的第一个元素； - 之后，驱动器开始旋转圆盘，每秒钟将指针移动到下一个元素，并累计所有指针经过的元素的和。由于圆盘是圆形的，在数组 $a$ 中，最后一个元素后面又是第一个元素； - 一旦累计的和至少为 $x$，驱动器就会关闭。 Polycarp 想进一步了解驱动器的工作方式，但他实在没有空。因此他请你帮忙回答 $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$。

第一行包含一个整数 $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$。

对于每个测试用例，输出一行包含 $m$ 个数字，第 $i$ 个数字表示： - 如果驱动器会无限工作，输出 $-1$； - 否则输出驱动器会工作的秒数。

由 ChatGPT 4.1 翻译