B. Большой массив и отрезки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Есть массив $$$a$$$, состоящий из $$$n$$$ целых положительных чисел и целое положительное число $$$k$$$. Из массива $$$a$$$ создается массив $$$b$$$ по следующим правилам:

  • массив $$$b$$$ содержит $$$n \cdot k$$$ чисел;
  • первые $$$n$$$ чисел массива $$$b$$$ совпадают с числами массива $$$a$$$, то есть $$$b_{i} = a_{i}$$$ для $$$i \le n$$$;
  • для любого $$$i \gt n$$$ выполняется $$$b_{i} = b_{i - n}$$$.

Например, если $$$a = [2, 3, 1, 4]$$$ и $$$k = 3$$$, то $$$b = [2, 3, 1, 4, 2, 3, 1, 4, 2, 3, 1, 4]$$$.

Дано число $$$x$$$. Необходимо посчитать количество таких позиций $$$l$$$ ($$$1 \le l \le n \cdot k$$$), для которых найдется такая позиция $$$r \ge l$$$, что сумма элементов массива $$$b$$$ на отрезке $$$[l, r]$$$ составит не менее $$$x$$$ (то есть $$$b_{l} + b_{l+1} + \dots + b_{r} \ge x$$$).

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^{4}$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит три целых числа $$$n$$$, $$$k$$$, $$$x$$$ ($$$1 \le n, k \le 10^{5}$$$; $$$1 \le x \le 10^{18}$$$).

Вторая строка каждого набора входных данных содержит $$$n$$$ целых положительных чисел $$$a_{i}$$$ ($$$1 \le a_{i} \le 10^{8}$$$).

Дополнительные ограничения на входные данные:

  • сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^{5}$$$;
  • сумма $$$k$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^{5}$$$.
Выходные данные

Для каждого набора входных данных выведите одно целое число — количество подходящих позиций $$$l$$$ в массиве $$$b$$$.

Пример
Входные данные
7
5 3 10
3 4 2 1 5
15 97623 1300111
105 95 108 111 118 101 95 118 97 108 111 114 97 110 116
1 100000 1234567891011
1
1 1 1
1
1 1 1
2
2 1 2
1 1
2 1 5
2 1
Выходные данные
12
1452188
0
1
1
1
0
Примечание

В первом наборе входных данных массив $$$b$$$ выглядит так:

$$$$$$[3, 4, 2, 1, 5, 3, 4, 2, 1, 5, 3, 4, 2, 1, 5]$$$$$$

Существует $$$12$$$ позиций $$$l$$$, для которых найдется подходящая позиция $$$r$$$. Вот некоторые (не все) из них:

  • $$$l = 1$$$, для которой есть позиция $$$r = 6$$$, сумма на отрезке $$$[1, 6]$$$ равна $$$18$$$;
  • $$$l = 2$$$, для которой есть позиция $$$r = 5$$$, сумма на отрезке $$$[2, 5]$$$ равна $$$12$$$;
  • $$$l = 6$$$, для которой есть позиция $$$r = 9$$$, сумма на отрезке $$$[6, 9]$$$ равна $$$10$$$.