← 返回题目列表

Codeforces · 1742/E

E. 斯库扎

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

Timur 有一个楼梯,有 $$$n$$$ 级台阶。第 $$$i$$$ 级台阶比前一个台阶高 $$$a_i$$$ 米。第一个台阶比地面高 $$$a_1$$$ 米,地面起始高度为 $$$0$$$ 米。

第一个测试用例的楼梯。

Timur 有 $$$q$$$ 问题,每个问题都用整数 $$$k_1, \dots, k_q$$$ 表示。对于每个问题 $$$k_i$$$,您必须打印如果 Timur 的腿长度为 $$$k_i$$$,他可以通过爬楼梯达到的最大可能高度。只有当 Timur 的腿长度至少为 $$$a_j$$$ 时,他才能爬上第 $$$j$$$ 级台阶。换句话说,$$$k_i \geq a_j$$$ 每爬升一步 $$$j$$$。

请注意,您应该独立回答每个问题。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 100$$$) — 测试用例的数量。

每个测试用例的第一行包含两个整数 $$$n, q$$$ ($$$1 \leq n, q \leq 2\cdot10^5$$$) - 分别是步骤数和问题数。

每个测试用例的第二行包含 $$$n$$$ 整数 ($$$1 \leq a_i \leq 10^9$$$) — 台阶的高度。

每个测试用例的第三行包含 $$$q$$$ 整数 ($$$0 \leq k_i \leq 10^9$$$) — 每个问题的数字。

保证$$$n$$$之和不超过$$$2\cdot10^5$$$,$$$q$$$之和不超过$$$2\cdot10^5$$$。

输出

对于每个测试用例,输出一行包含 $$$q$$$ 整数,即每个问题的答案。

请注意,某些问题的答案不适合 32 位整数类型,因此您应该在编程语言中至少使用 64 位整数类型(例如 C++ 的 long long)。

示例

输入 #1

3
4 5
1 2 1 5
1 2 4 9 10
2 2
1 1
0 1
3 1
1000000000 1000000000 1000000000
1000000000

输出 #1

1 4 4 9 9 
0 2 
3000000000

注意

考虑第一个测试用例,如声明中所示。

- 如果 Timur 的腿长 $$$1$$$,那么他只能爬楼梯 $$$1$$$,所以他能到达的最高高度是 $$$1$$$ 米。
- 如果 Timur 的腿长度为 $$$2$$$ 或 $$$4$$$,那么他只能爬楼梯 $$$1$$$、$$$2$$$ 和 $$$3$$$,所以他能爬到的最高高度是 $$$1+2+1=4$$$ 米。
- 如果 Timur 的腿长 $$$9$$$ 或 $$$10$$$,那么他可以爬上整个楼梯,所以他能到达的最高高度是 $$$1+2+1+5=9$$$ 米。