На столе в ряд выложено $n$ кучек кубиков, в $i$-й кучке ($1 \le i \le n$) изначально находится $a_i$ кубиков.

Маленький Т и маленький S предоставили два магических сита с размером ячеек $p$ и $q$ соответственно, которые позволяют массово уменьшать количество кубиков в кучках путем взятия остатка от деления. В естественном развернутом состоянии каждое сито покрывает ровно $k$ кучек кубиков. Сита обладают особой эластичностью: их можно свободно растягивать в обе стороны, чтобы покрыть больший диапазон, но нельзя сжимать. Использование магического сита происходит следующим образом:

• Выберите непрерывный отрезок кучек $[l, r]$ длиной не менее $k$ и наложите на него сито;
• Выберите одно из двух магических сит, то есть выберите $m \in \{p, q\}$;
• Для каждой кучки в отрезке $[l, r]$ замените количество кубиков на остаток от деления на $m$, то есть выполните $a_i \leftarrow a_i \pmod m$.

Поскольку вы участвуете в этой игре, вы, конечно, не удовлетворены посредственным результатом. Чтобы занять первое место в таблице лидеров, вы хотите узнать, какое минимальное общее количество кубиков ($\sum_{i=1}^n a_i$) может остаться на столе после произвольного количества применений магических сит.

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

Каждый тест содержит несколько наборов входных данных. В первой строке содержится целое число $T$ ($1 \le T \le 10^3$), количество наборов данных. Для каждого набора данных:

• Первая строка содержит четыре целых числа $n, k, p, q$ ($1 \le k \le n \le 10^5$, $1 \le p < q \le 10^9$), обозначающих количество кучек, минимальную ширину покрытия сита и размеры ячеек двух магических сит.
• Вторая строка содержит $n$ целых чисел $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$), обозначающих начальное количество кубиков в каждой кучке.

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

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

Для каждого набора данных выведите одну строку, содержащую одно неотрицательное целое число — минимальное общее количество кубиков, оставшихся на столе.

Примеры

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

6
1 1 3 4
2
3 2 10 20
3 1 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

1
11
3
0
4
569

Примечание

Для второго набора данных один из способов достичь минимального общего количества кубиков, равного 11:

• Выберите отрезок $[1, 4]$ и используйте магическое сито с размером ячеек 10, количество кубиков становится $[1, 1, 9]$.

Для третьего набора данных один из способов достичь минимального общего количества кубиков, равного 3:

• Выберите отрезок $[2, 4]$ и используйте магическое сито с размером ячеек 4, количество кубиков становится $[1, 2, 3, 0]$;
• Выберите отрезок $[1, 3]$ и используйте магическое сито с размером ячеек 3, количество кубиков становится $[1, 2, 0, 0]$.