B. Отрезки для всех пар
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
Shirobon - FOX
⠀

Вам даны $$$n$$$ точек на оси $$$x$$$ с возрастающими целыми положительными координатами $$$x_1 < x_2 < \ldots < x_n$$$.

Для каждой пары $$$(i, j)$$$, такой что $$$1 \leq i < j \leq n$$$, строится отрезок $$$[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$$$-й запрос.

Пример
Входные данные
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
Выходные данные
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$$$ отрезках.