Sigma Queries#13037
You're given an array of length : a_1,a_2,...,a_n and you're begin asked queries about it As following :
let \displaystyle b=\underbrace{a \cup a \cup a \cup ... \cup a}_{\infty \text{ number of times}} where denotes unification (concatenation).
Per each query , you're given an integer , You're asked the determine the minimum index such that \sum\limits_{i=1}^k b_i \ge x or determine it's impossible .
The first line contains single integer (1 \le t \le 10^4) — the number of test cases.
The first line of each test case contains two integers (1 \le n,q \le 2\cdot 10^5) — the length of array and the number of queries respectively.
The second line contains integers a_1,a_2,..,a_n (1 \le a_1,a_2,...,a_n \le 10^9) — the array .
The third line contains integers x_1,x_2,...,x_q (1 \le x_1,x_2,..,x_q \le 10^{18}) — the queries.
It's guaranteed that sum of n+q overall tests doesn't exceed 4 \cdot 10^5.
For each test case , answer i_1,i_2,...,i_q each denoting the answer for the i_{\text{th}} query respectively.
Example 1
Subtask ( points) : (1 \le n,q \le 1000).
Subtask ( points) : (1 \le x_1,x_2,...,x_q \le \sum\limits_{i=1}^n a_i)
Subtask ( points) : No additional constraints