积木消除游戏
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

> 欣赏完绚丽的幻光留影，大家又被不远处的积木消除小游戏区吸引了目光。 > > 桌面上整齐排列着五颜六色的积木。小 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 \gets a_i \bmod m$$$。

既然参与了这场游戏，你自然不满足于平庸的成绩。为了在排行榜上拔得头筹，你想知道，通过反复使用任意次数的魔法筛网，最终桌面上剩余的积木总数（即 $$$\sum_{i = 1} ^ n a_i$$$）最少能被消除到多少？

Input

每个测试点中包含多组测试数据。输入的第一行包含一个正整数 $$$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)$$$，分别表示积木的堆数、筛网自然展开时跨越的积木堆数，以及两个魔法筛网的网眼大小。 - 第二行包含 $$$n$$$ 个正整数 $$$a_1, a_2, \dots, a_n \ (1 \le a_i \le 10 ^ 9)$$$，分别表示每堆积木的初始数量。

保证所有测试数据中 $$$n$$$ 的和不超过 $$$10 ^ 5$$$。

Output

对于每组测试数据，输出一行一个非负整数，表示桌面上剩余总积木数量的最小值。

Example

Input
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
Output
1
11
3
0
4
569

Note

对于第二组测试数据，一种能使桌面上剩余积木总数达到最小值 $$$11$$$ 的操作方式如下：

- 选定区间 $$$[1, 4]$$$ 并使用网眼大小为 $$$10$$$ 的魔法筛网，剩余的积木数量变为 $$$[1, 1, 9]$$$。

对于第三组测试数据，一种能使桌面上剩余积木总数达到最小值 $$$3$$$ 的操作方式如下：

- 选定区间 $$$[2, 4]$$$ 并使用网眼大小为 $$$4$$$ 的魔法筛网，剩余的积木数量变为 $$$[1, 2, 3, 0]$$$； - 选定区间 $$$[1, 3]$$$ 并使用网眼大小为 $$$3$$$ 的魔法筛网，剩余的积木数量变为 $$$[1, 2, 0, 0]$$$。