Вам даны два массива \(a_1, a_2, \ldots, a_n\) и \(b_1, b_2, \ldots, b_n\).
Вы должны выполнить следующую операцию ровно один раз:
- выбрать любые индексы \(l\) и \(r\) такие, что \(1 \le l \le r \le n\);
- поменять местами \(a_i\) и \(b_i\) для всех \(i\) таких, что \(l \leq i \leq r\).
Найдите максимально возможное значение \(\text{gcd}(a_1, a_2, \ldots, a_n) + \text{gcd}(b_1, b_2, \ldots, b_n)\) после выполнения операции ровно один раз. Также найдите количество различных пар \((l, r)\), для которых достигается максимальное значение.
Выходные данные
Для каждого набора входных данных выведите два целых числа: максимальное значение \(\text{gcd}(a_1, a_2, \ldots, a_n) + \text{gcd}(b_1, b_2, \ldots, b_n)\) после выполнения операции ровно один раз, и количество подходящих пар.
Примечание
В первом, третьем и четвертом наборах входных данных ни в одном из массивов нельзя получить НОД больше \(1\), поэтому ответ — \(1 + 1 = 2\). Любая пара \((l, r)\) достигает одинаковый результат, например, в первом примере \(36\) такиз пар.
В последнем наборе входных данных нужно выбрать \(l = 1\), \(r = 2\) для максимизации ответа. В этом случае НОД в первом массиве будет\(5\), а во втором — \(1\), поэтому ответ равен \(5 + 1 = 6\), а количество пар равно \(1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
8
11 4 16 17 3 24 25 8
8 10 4 21 17 18 25 21
4
6 4 24 13
15 3 1 14
2
13 14
5 8
8
20 17 15 11 21 10 3 7
9 9 4 20 14 9 13 1
2
18 13
15 20
|
2 36
3 2
2 3
2 36
6 1
|