朵拉刚刚学会了编程语言C++!
然而,她完全误解了C++的含义。她将其视为数组 $$$c$$$ 与 $$$n$$$ 元素的两种添加操作。朵拉有两个整数 $$$a$$$ 和 $$$b$$$。在一次操作中,她可以选择执行以下操作之一。
- 选择一个整数$$$i$$$,使得$$$1 \leq i \leq n$$$,并将$$$c_i$$$增加$$$a$$$。
- 选择一个整数$$$i$$$,使得$$$1 \leq i \leq n$$$,并将$$$c_i$$$增加$$$b$$$。
请注意,$$$a$$$ 和 $$$b$$$ 是常量,并且它们可以相同。
让我们将数组 $$$d$$$ 的范围定义为 $$$\max(d_i) - \min(d_i)$$$。例如,数组 $$$[1, 2, 3, 4]$$$ 的范围是 $$$4 - 1 = 3$$$,数组 $$$[5, 2, 8, 2, 2, 1]$$$ 的范围是 $$$8 - 1 = 7$$$,数组 $$$[3, 3, 3]$$$ 的范围是 $$$3 - 3 = 0$$$。
经过任意次数的操作(可能是 $$$0$$$),Dora 计算新数组的范围。你需要帮助朵拉最小化这个值,但由于朵拉喜欢自己探索,所以你只需要告诉她最小化的值即可。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含三个整数 $$$n$$$、$$$a$$$ 和 $$$b$$$ ($$$1 \leq n \leq 10^5$$$, $$$1 \leq a, b \leq 10^9$$$) — 分别是数组 $$$c$$$ 的长度和常量值。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$c_1, c_2, \ldots, c_n$$$ ($$$1 \leq c_i \leq 10^9$$$) — 数组 $$$c$$$ 的初始元素。
保证所有测试用例的$$$n$$$总和不超过$$$10^5$$$。
输出
对于每个测试用例,输出一个整数 - 任意次数操作后数组的最小可能范围。
示例
输入 #1
10 4 5 5 1 3 4 4 4 2 3 1 3 4 6 4 7 7 1 1 2 6 3 15 9 1 9 5 3 18 12 1 4 5 7 27 36 33 13 23 12 35 24 41 10 6 9 15 5 6 9 8 2 12 15 3 8 2 1 1000000000 1 1000000000 6 336718728 709848696 552806726 474775724 15129785 371139304 178408298 13106071 6 335734893 671469786 138885253 70095920 456876775 9345665 214704906 375508929
输出 #1
3 0 3 2 3 5 1 0 17 205359241
注意
在第一个测试用例中,我们可以将 $$$c_1 = 1$$$ 增加 $$$a = 5$$$。数组$$$c$$$将变为$$$[6, 3, 4, 4]$$$,范围为$$$3$$$。请注意,得出答案的方法不止一种。
在第二个测试用例中,我们可以将 $$$c_1 = 1$$$ 增加 $$$a = 2$$$,然后将 $$$c_1 = 3$$$ 增加 $$$b = 3$$$。另外,我们可以将 $$$c_2 = 3$$$ 增加 $$$b = 3$$$,并将 $$$c_3 = 4$$$ 增加 $$$a = 2$$$。数组$$$c$$$将变为$$$[6, 6, 6, 6]$$$,范围为$$$0$$$。