Поликарп планирует пройти полное медицинское обследование в местной поликлинике. В него входит прохождение \(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\) врачей, не пропуская ни одной минуты и не проходя ни одного врача повторно. Если существует несколько ответов, то выведите любой из них.
Выходные данные
На каждый набор входных данных выведите ответ.
Если существует такая минута \(x\) и перестановка \(p\), что Поликарп сможет посетить всех \(n\) врачей, не пропуская ни одной минуты и не проходя ни одного врача повторно, то в первой строке выведите \(x\), а во второй — перестановку \(p\). Если существует несколько ответов, то выведите любой из них.
В противном случае выведите \(-1\) в единственной строке.
Примечание
В третьем наборе входных данных невозможно посетить все врачей, потому что Поликарп должен посетить врача \(2\) в минуту \(2\) и врача \(1\) в минуту \(4\). Однако, для этого ему придется подождать минуту между посещениями, что запрещено.
В четвертом наборе входных данных все врачи принимают пациентов в течение одних и тех же \(2\) минут. Однако, так как их трое, Поликарп не сможет посетить их всех.
Примеры
| № | Входные данные | Выходные данные |
|
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
|