Начинающего сотрудника Василия часто отправляют на курсы повышения квалификации в различные города. В ближайшее время ему предстоит съездить на $$$N$$$ таких курсов. Для каждой поездки известен диапазон дней и город, в котором Василий в эти дни должен находиться.
К сожалению, начальство иногда ошибается при планировании, поэтому не исключена ситуация, что в какой-то день Василий должен находиться в двух (или более) разных городах одновременно. Напишите программу, которая найдёт номер первого такого дня.
В первой строке записано количество поездок на курсы $$$N$$$ ($$$2 \le N \le 10^5$$$).
В каждой из следующих $$$N$$$ строк через пробел записаны день начала $$$d_1$$$ и день конца $$$d_2$$$ очередных курсов ($$$1 \le d_1 \le d_2 \le 10^9$$$) и номер города $$$c$$$, где они проводятся ($$$1 \le c \le 10^9$$$). Входные данные упорядочены по неубыванию $$$d_1$$$.
Выведите одно целое число — номер первого дня, в который Василий должен оказаться одновременно в двух (или более) разных городах. Если такого дня нет, то выведите 0.
Решения, работающие при $$$N \le 1000$$$, $$$d_2 \le 1000$$$, будут оцениваться из 50 баллов.
3 1 7 5 2 4 5 3 5 2
3
Будем считать, что все города находятся недалеко друг от друга, поэтому время на дорогу в этой задаче не учитывается.
Примечание для пишущих на Python: три числа, записанных через пробел, можно прочитать так:
d1, d2, c = map(int, input().split())
