C. Дора и C++
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дора только что научилась языку программирования 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$$$) Дора вычисляет диапазон нового массива. Вам нужно помочь Доре минимизировать это значение, но поскольку Дора любит исследовать всё самостоятельно, вам нужно сказать ей только само минимальное значение.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$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$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — минимально возможный диапазон массива после какого-то количества операций.

Пример
Входные данные
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
Выходные данные
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$$$.