Поликарп разбирал свой чердак и нашел на нем старый дисковод. В дисковод был вставлен круглый диск, на котором было написано \(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\).
Выходные данные
Для каждого набора входных данных на отдельной строке выведите \(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
|
0 6 2
-1 -1
1 3
|