Таня любит мультфильмы. В прокате ожидаются \(n\) мультфильмов, и \(i\)-й из них будет показываться в ее любимом кинотеатре со дня \(a_i\) по день \(b_i\) (\(1 \le a_i \le b_i \le 10^9\)).
В кинотеатре действует особая акция: в любой день, в который в прокате идёт ровно один мультфильм, кинотеатр даёт существенную скидку на сеанс.
Тане не важно, какой мультфильм посмотреть, но она хочет сэкономить, поэтому просит Вас найти любой такой день \(x\), что в этот день в прокате идёт ровно один мультфильм. Формально: для выбранного \(x\) должно быть верно, что существует ровно одно такое \(i\) (\(1 \le i \le n\)), что \(a_i \le x \le b_i\). Если ответов несколько, то выведите любой. Если такого дня не существует, то выведите -1.
Выходные данные
Для каждого из \(t\) наборов входных данных в порядке их записи в тесте выведите ответ. В качестве ответа на \(i\)-й набор выведите любое такое \(x\), что в день \(x\) в прокате идёт ровно один мультфильм. Если таких дней не существует, то выведите -1.
Примечание
Третий набор входных данных: в дни \(1\) и \(2\), первый и третий мультфильмы будут в прокате, а в дни \(3\) и \(4\) — второй и третий. Таким образом, нет такого дня, когда только один мультфильм будет в прокате.
В четвертом тесте \(11\) также является возможным ответом.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1
1 1
3
2 1000000000
2 500000000
500000002 1000000000
3
1 2
3 4
1 4
2
4 11
4 9
3
1 5
10 10
1 5
|
1
500000001
-1
10
10
|