← 返回题目列表

Codeforces · 2007/C

C. 朵拉和C++

中文机器翻译题面 查看原题

朵拉刚刚学会了编程语言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$$$。