← 返回题目列表

Codeforces · 1490/G

G. 旧软盘驱动器

中文机器翻译题面 查看原题

波利卡普正在拆除他的阁楼,并在上面发现了一个旧软盘驱动器。将一张圆盘插入驱动器,上面写有 $$$n$$$ 整数。

Polycarp 将磁盘上的数字写入 $$$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$$$。

输入

第一行包含一个整数 $$$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$$$ 如果驱动器无限运行;
- 驱动器将运行的秒数,否则。

示例

输入 #1

3
3 3
1 -3 4
1 5 2
2 2
-2 0
1 2
2 2
0 1
1 2

输出 #1

0 6 2 
-1 -1 
1 3