題目背景

欣賞完絢麗的幻光留影，大家又被不遠處的積木消除小遊戲區吸引了目光。

桌面上整齊排列著五顏六色的積木。小 T 和小 S 作為攤主，各自提供了一個能夠批量消除積木的魔法篩網。遊戲規則很簡單：大家可以反覆使用這兩個篩網進行消除，最終根據桌面上剩餘總積木數量進行排名。

桌面上整齊排列著 $n$ 堆積木，第 $i$ ($1 \le i \le n$) 堆的初始數量為 $a_i$。

小 T 和小 S 分別提供了網眼大小為 $p, q$ 的兩個魔法篩網，能將覆蓋的積木堆按對應的模數取餘，從而將積木批量消除。在自然展開時，這兩個篩網都恰好跨越 $k$ 堆積木的寬度。它們具有特殊的彈性，可以向兩端自由拉伸以覆蓋更長的範圍，但無法向內壓縮收攏。魔法篩網的使用方式如下：

• 選定一段長度至少為 $k$ 的連續積木區間 $[l, r]$ 並鋪上篩網；
• 從兩個魔法篩網中任選一個，即選定 $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 0 26
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

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]$。