Дора только что научилась языку программирования 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\)) Дора вычисляет диапазон нового массива. Вам нужно помочь Доре минимизировать это значение, но поскольку Дора любит исследовать всё самостоятельно, вам нужно сказать ей только само минимальное значение.
Выходные данные
Для каждого набора входных данных выведите одно целое число — минимально возможный диапазон массива после какого-то количества операций.
Примечание
В первом наборе входных данных мы можем увеличить \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
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
|
3
0
3
2
3
5
1
0
17
205359241
|