409368: GYM103492 E Monopoly

Little Rabbit loves playing a tabletop game called Monopoly. In the game, players roll the dice to move around the game board, buying and trading properties, and developing them with houses and hotels. Players collect rent from their opponents, with the goal being to drive them into bankruptcy.

One day, Little Rabbit invites Little Horse to play the game with him, but Little Horse stands him up. As a result, Little Rabbit can only play the game on his own. After a while, Little Rabbit finds out another way to play the game.

Let's consider the map of the game as $$$n$$$ integers $$$a_1,a_2,\dots,a_n$$$ placed in a circle. If the player lands on $$$a_i$$$, his score will change by $$$a_i$$$ points. Specifically, if $$$a_i>0$$$, his score will increase by $$$|a_i|$$$ points. If $$$a_i<0$$$, his score will decrease by $$$|a_i|$$$ points. And of course, if $$$a_i=0$$$, his score won't change.

As there is nobody else, Little Rabbit doesn't feel like rolling a dice. So he just moves on the map step by step. Formally, if he now lands on $$$a_i$$$ and $$$i<n$$$, he will move to $$$a_{i+1}$$$ in the next step. If he now lands on $$$a_n$$$, he will move to $$$a_1$$$ in the next step.

Initially, Little Rabbit has $$$0$$$ points, and his first step is to land on $$$a_1$$$. Little Rabbit wonders how many steps he should take at least to reach exactly $$$x$$$ points. (Specifically, since his initial score is $$$0$$$, he needs $$$0$$$ steps to reach $$$0$$$ points.)

The first line of the input contains an integer $$$T$$$ ($$$1 \le T \le 20$$$), indicating the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n,m \le 10^5$$$), indicating the number of integers on the map and the number of queries.

The second line contains $$$n$$$ integers $$$a_1,a_2,\dots,a_n$$$ ($$$-10^9\le a_1,a_2,\dots,a_n \le 10^9$$$), indicating the integers on the map.

In the next $$$m$$$ lines, each line contains an integer $$$x$$$ ($$$-10^{12} \le x \le 10^{12}$$$), indicating a query.

It's guaranteed that $$$\sum n \le 5\times10^5$$$ and $$$\sum m \le 5\times10^5$$$.

For each query, output an integer in a single line, indicating the number of steps he should take at least to reach exactly $$$x$$$ points. If it is impossible to reach exactly $$$x$$$ points, output $$$-1$$$.

1
3 5
1 -3 4
1
5
2
0
-10

1
7
3
0
-1