G. Старый дисковод
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Поликарп разбирал свой чердак и нашел на нем старый дисковод. В дисковод был вставлен круглый диск, на котором было написано $$$n$$$ целых чисел.

Поликарп выписал числа с диска в массив $$$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$$$, если дисковод будет работать бесконечно долго;
  • количество секунд, в течение которых будет работать дисковод, в противном случае.
Пример
Входные данные
3
3 3
1 -3 4
1 5 2
2 2
-2 0
1 2
2 2
0 1
1 2
Выходные данные
0 6 2 
-1 -1 
1 3