Вам задано масив довжини : a_1,a_2,...,a_n і вам ставлять запитів про нього наступним чином:
Нехай \displaystyle b=\underbrace{a \cup a \cup a \cup ... \cup a}_{\infty \text{ разів}}, де позначає об'єднання (конкатенацію).
У кожному запиті вам задається ціле число , і вас просять визначити мінімальний індекс такий, що \sum\limits_{i=1}^k b_i \ge x, або визначити, що це неможливо, вивівши .
Перший рядок містить одне ціле число (1 \le t \le 10^4) — кількість тестових випадків.
Перший рядок кожного тестового випадку містить два цілих числа (1 \le n,q \le 2\cdot 10^5) — довжину масиву та кількість запитів відповідно.
Другий рядок містить цілих чисел a_1,a_2,..,a_n (1 \le a_1,a_2,...,a_n \le 10^9) — масив .
Третій рядок містить цілих чисел x_1,x_2,...,x_q (1 \le x_1,x_2,..,x_q \le 10^{18}) — запити.
Гарантується, що сума n+q по всіх тестах не перевищує 4 \cdot 10^5.
Для кожного тестового випадку виведіть відповіді i_1,i_2,...,i_q, кожна з яких позначає відповідь на i_{\text{ий}} запит відповідно.
Приклад 1
Підзадача ( балів) : (1 \le n,q \le 1000).
Підзадача ( балів) : (1 \le x_1,x_2,...,x_q \le \sum\limits_{i=1}^n a_i)
Підзадача ( балів) : Без додаткових обмежень