您将在 $$$x$$$ 轴上获得 $$$n$$$ 点,递增的正整数坐标 $$$x_1 < x_2 < \ldots < x_n$$$。
对于 $$$1 \leq i < j \leq n$$$ 的每对 $$$(i, j)$$$,绘制线段 $$$[x_i, x_j]$$$。这些线段是闭合的,即线段 $$$[a, b]$$$ 包含点 $$$a, a+1, \ldots, b$$$。
您收到 $$$q$$$ 查询。在第 $$$i$$$ 查询中,您将获得一个正整数 $$$k_i$$$,并且您必须确定 $$$k_i$$$ 段中包含多少个具有整数坐标的点。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$、$$$q$$$ ($$$2 \le n \le 10^5$$$, $$$1 \le q \le 10^5$$$) — 点数和查询数。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$x_1, x_2, \ldots, x_n$$$ ($$$1 \leq x_1 < x_2 < \ldots < x_n \leq 10^9$$$) — $$$n$$$ 点的坐标。
每个测试用例的第三行包含 $$$q$$$ 整数 $$$k_1, k_2, \ldots, k_q$$$ ($$$1 \leq k_i \leq 10^{18}$$$) — $$$q$$$ 查询的参数。
保证所有测试用例的$$$n$$$总和不超过$$$10^5$$$,所有测试用例的$$$q$$$总和不超过$$$10^5$$$。
输出
对于每个测试用例,输出一行包含 $$$q$$$ 整数:第 $$$i$$$ 个整数是第 $$$i$$$ 个查询的答案。
示例
输入 #1
3 2 2 101 200 2 1 6 15 1 2 3 5 6 7 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 5 8 254618033 265675151 461318786 557391198 848083778 6 9 15 10 6 9 4 4294967300
输出 #1
0 100 0 0 0 0 2 0 0 0 3 0 2 0 0 0 0 291716045 0 0 0 291716045 0 301749698 0
注意
在第一个示例中,您仅绘制线段 $$$[101, 200]$$$。没有点恰好包含在 $$$2$$$ 段中,并且 $$$100$$$ 点 $$$101, 102, \ldots, 200$$$ 恰好包含在 $$$1$$$ 段中。
在第二个示例中,绘制 $$$15$$$ 线段:$$$[1, 2], [1, 3], [1, 5], [1, 6], [1, 7], [2, 3], [2, 5], [2, 6], [2, 7], [3, 5], [3, 6], [3, 7], [5, 6]、[5, 7]、[6, 7]$$$。点 $$$1, 7$$$ 恰好包含在 $$$5$$$ 段中;点 $$$2, 4, 6$$$ 恰好包含在 $$$9$$$ 段中;点 $$$3, 5$$$ 恰好包含在 $$$11$$$ 段中。