I. Медицинское обследование
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Поликарп планирует пройти полное медицинское обследование в местной поликлинике. В него входит прохождение $$$n$$$ врачей. Врачи пронумерованы от $$$1$$$ до $$$n$$$. $$$i$$$-й врач принимает пациентов с минуты $$$L_i$$$ по минуту $$$R_i$$$, поэтому Поликарп может прийти к нему в любую минуту из этого интервала. Каждый врач тратит одну минуту, чтобы проверить здоровье Поликарпа.

Поликарп хочет прийти в поликлинику в некоторую минуту $$$x$$$ и посетить всех $$$n$$$ врачей в некотором порядке, не пропуская ни одной минуты и не проходя ни одного врача повторно.

Более формально, он выбирает некоторое целое число $$$x$$$ и перестановку $$$p_1, p_2, \dots, p_n$$$ (последовательность из $$$n$$$ целых чисел от $$$1$$$ до $$$n$$$ такую, что каждое число встречается ровно один раз), затем посещает:

  • врача $$$p_1$$$ в минуту $$$x$$$;
  • врача $$$p_2$$$ в минуту $$$x+1$$$;
  • ...
  • врача $$$p_n$$$ в минуту $$$x+n-1$$$.

$$$p_i$$$-й врач должен принимать пациентов в минуту $$$x+i-1$$$, то есть должно выполняться следующее: $$$L[p_i] \le x + i - 1 \le R[p_i]$$$.

Определите, может ли Поликарп выбрать такую минуту $$$x$$$ и перестановку $$$p$$$, что он сможет посетить всех $$$n$$$ врачей, не пропуская ни одной минуты и не проходя ни одного врача повторно. Если существует несколько ответов, то выведите любой из них.

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

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

Затем следуют описания $$$t$$$ наборов входных данных.

В первой строке каждого набора входных данных записано одно целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — количество врачей.

Во второй строке каждого набора входных данных записаны $$$n$$$ целых чисел $$$L_1, L_2, \dots L_n$$$ ($$$1 \le L_i \le 10^9$$$).

В третьей строке каждого набора входных данных записаны $$$n$$$ целых чисел $$$R_1, R_2, \dots R_n$$$ ($$$L_i \le R_i \le 10^9$$$).

Сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

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

На каждый набор входных данных выведите ответ.

Если существует такая минута $$$x$$$ и перестановка $$$p$$$, что Поликарп сможет посетить всех $$$n$$$ врачей, не пропуская ни одной минуты и не проходя ни одного врача повторно, то в первой строке выведите $$$x$$$, а во второй — перестановку $$$p$$$. Если существует несколько ответов, то выведите любой из них.

В противном случае выведите $$$-1$$$ в единственной строке.

Пример
Входные данные
5
3
2 3 1
3 3 2
8
6 6 5 4 9 4 3 6
7 6 10 6 9 6 6 8
2
4 2
4 2
3
2 2 2
3 3 3
1
5
10
Выходные данные
1
3 1 2 
3
7 4 6 2 1 8 5 3 
-1
-1
7
1
Примечание

В третьем наборе входных данных невозможно посетить все врачей, потому что Поликарп должен посетить врача $$$2$$$ в минуту $$$2$$$ и врача $$$1$$$ в минуту $$$4$$$. Однако, для этого ему придется подождать минуту между посещениями, что запрещено.

В четвертом наборе входных данных все врачи принимают пациентов в течение одних и тех же $$$2$$$ минут. Однако, так как их трое, Поликарп не сможет посетить их всех.