A. Отрезки по модулю
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив $$$a$$$, состоящий из $$$n$$$ целых чисел, а также параметр $$$k$$$ и множество целых чисел $$$M=\{p, q\}$$$.

Вы можете выполнять следующую операцию над $$$a$$$ произвольное число раз (возможно, ноль):

  • Сначала выберите отрезок $$$[l,r]$$$ ($$$1 \le l \le r \le n$$$) длины не менее $$$k$$$ (то есть $$$r-l+1\ge k$$$) и целое число $$$m \in M$$$;
  • Затем для каждого $$$l \le i \le r$$$ присвойте $$$a_i \gets a_i \bmod m$$$.

Требуется найти минимально возможное значение $$$\sum \limits_{i=1}^n a_i$$$ после выполнения всех операций.

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

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

Первая строка каждого набора входных данных содержит четыре целых числа $$$n$$$, $$$k$$$, $$$p$$$ и $$$q$$$ ($$$1\le k\le n\le 10^5$$$, $$$1\le p \lt q\le 10^9$$$) — длину массива $$$a$$$, параметр и элементы множества $$$M$$$.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1\le a_i\le 10^9$$$) — элементы массива $$$a$$$.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

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

Для каждого набора входных данных выведите одно целое число — минимально возможное значение $$$\sum \limits_{i=1}^n a_i$$$ после выполнения всех операций.

Пример
Входные данные
6
1 1 3 4
2026
3 2 10 20
31 41 59
4 3 3 4
1 2 3 4
6 4 9 20
18 27 180 9 45 99
7 4 3 5
6 7 14 12 100 78 4
9 4 244 353
9982 4435 3998 2443 5399 8244 3539 9824 4353
Выходные данные
1
11
3
0
4
569
Примечание

Во втором наборе входных данных один из возможных способов получить $$$\sum \limits_{i=1}^n a_i=11$$$ состоит в применении следующей операции к $$$a$$$:

  1. Выберите $$$[l,r]=[1,3]$$$ и $$$m=10$$$, тогда $$$a$$$ станет $$$[1,1,9]$$$.

В третьем наборе входных данных один из возможных способов получить $$$\sum \limits_{i=1}^n a_i=3$$$ состоит в применении следующих операций к $$$a$$$:

  1. Выберите $$$[l,r]=[1,4]$$$ и $$$m=4$$$, тогда $$$a$$$ станет $$$[1,2,3,0]$$$;
  2. Выберите $$$[l,r]=[2,4]$$$ и $$$m=3$$$, тогда $$$a$$$ станет $$$[1,2,0,0]$$$.