Сигма-запити#13037

Сигма-запити

1 секунда
256 мегабайтів
Середня

Вам задано масив довжини : 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

Loading
Loading

Оцінювання

  1. Підзадача ( балів) : (1 \le n,q \le 1000).

  2. Підзадача ( балів) : (1 \le x_1,x_2,...,x_q \le \sum\limits_{i=1}^n a_i)

  3. Підзадача ( балів) : Без додаткових обмежень