G. Сакура Адачи и оптимальные последовательности
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Адачи находится на грани краха... из-за, эээ, этой задачи! Да, это точно... в любом случае, пожалуйста, помогите ей решить её!

Вам даны два массива $$$a$$$ и $$$b$$$ длины $$$n$$$ ($$$1\leq a_i\leq b_i$$$).

За одну операцию вы можете выбрать одно действие из двух:

  • выбрать индекс $$$i$$$ ($$$1\leq i\leq n$$$) и присвоить $$$a_i := a_i + 1$$$
  • удвоить все элементы массива $$$a$$$.

Обозначим $$$x$$$ как минимальное количество операций, необходимых для того, чтобы сделать $$$a = b$$$. Два массива $$$a$$$ и $$$b$$$ длины $$$n$$$ считаются равными, если $$$a_i = b_i$$$ для всех $$$1\leq i\leq n$$$.

Найдите значение $$$x$$$. Кроме того, подсчитайте количество последовательностей операций, которые делают $$$a = b$$$, используя ровно $$$x$$$ операций. Две такие последовательности операций считаются различными, если для некоторого $$$1\leq j\leq x$$$, $$$j$$$-я операция отличается (либо по типу выбранной операции, либо по выбранному индексу, если это применимо).

Поскольку количество последовательностей может быть большим, выведите его по модулю $$${\color{red}{10^6+3}}$$$. Обратите внимание, что $$$10^6+3$$$ является простым числом.

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

Первая строка содержит одно целое число $$$t$$$ ($$$1\leq t\leq 10^4$$$)  — количество наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2\leq n\leq 2\cdot 10^5$$$).

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел, $$$a_1, a_2, \dots, a_n$$$ ($$$1\leq a_i\leq 10^6$$$).

Третья строка каждого набора входных данных содержит $$$n$$$ целых чисел, $$$b_1, b_2, \dots, b_n$$$ ($$$a_i\leq b_i\leq 10^6$$$).

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2\cdot 10^5$$$.

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

Для каждого набора входных данных выведите два целых числа: значение $$$x$$$ и количество последовательностей операций, которые делают $$$a = b$$$, используя ровно $$$x$$$ операций, по модулю $$$10^6+3$$$. Значение $$$x$$$ должно быть выведено точно; то есть, оно не должно быть взято по модулю $$$10^6 + 3$$$.

Пример
Входные данные
8
6
1 3 6 4 3 2
3 7 10 4 4 8
2
1 1
4 3
5
2 3 2 5 1
18 13 10 30 7
5
5 4 3 6 2
100 125 231 113 107
4
2 2 2 2
2 2 2 2
4
1 1 1 1
2 2 2 2
7
1 1 1 1 1 1 200000
200000 200000 200000 200000 200000 200000 200000
3
542264 174876 441510
641112 325241 995342
Выходные данные
17 827116
3 1
12 288
35 567812
0 1
1 1
1199994 0
803045 366998
Примечание

Во втором примере возможно преобразовать $$$a$$$ в $$$b$$$, используя только три операции. Существует только один способ сделать это, а именно:

  • Добавьте $$$1$$$ к $$$a_1$$$, получая $$$a = [2, 1]$$$. Затем удвойте все элементы массива $$$a$$$, получая $$$a = [4, 2]$$$. Затем добавьте $$$1$$$ к $$$a_2$$$, получая $$$a = [4, 3]$$$. Тогда мы имеем, что $$$a = b$$$, как и требовалось.

Можно показать, что невозможно преобразовать $$$a$$$ в $$$b$$$, используя менее трёх операций.