给定一个由 $$$n$$$ 整数组成的数组 $$$a$$$,以及一个参数 $$$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$$$ 的最小可能值。
示例
输入复制
61 1 3 420263 2 10 2031 41 594 3 3 41 2 3 46 4 9 2018 27 180 9 45 997 4 3 56 7 14 12 100 78 49 4 244 3539982 4435 3998 2443 5399 8244 3539 9824 4353
输出复制
111304569
注意
在第二个测试用例中,获取 $$$\sum \limits_{i=1}^n a_i=11$$$ 的可能方法是将以下操作应用于 $$$a$$$:
- 选择$$$[l,r]=[1,3]$$$ 和$$$m=10$$$,则$$$a$$$ 变为$$$[1,1,9]$$$。
在第三个测试用例中,获取 $$$\sum \limits_{i=1}^n a_i=3$$$ 的可能方法是将以下操作应用于 $$$a$$$:
- 选择$$$[l,r]=[1,4]$$$且$$$m=4$$$,则$$$a$$$变为$$$[1,2,3,0]$$$;
- 选择$$$[l,r]=[2,4]$$$ 和$$$m=3$$$,则$$$a$$$ 变为$$$[1,2,0,0]$$$。