5. Business Trips to Courses
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The novice employee Vasily is often sent on professional development courses in various cities. In the near future, he is scheduled to attend $$$N$$$ such courses. For each trip, the range of days and the city where Vasily must be present are known.

Unfortunately, the management sometimes makes mistakes in planning, so it is possible that on some day Vasily is supposed to be in two (or more) different cities at the same time. Write a program that will find the number of the first such day.

Input

The first line contains the number of trips to the courses $$$N$$$ ($$$2 \le N \le 10^5$$$).

In each of the following $$$N$$$ lines, the start day $$$d_1$$$, the end day $$$d_2$$$ of the next courses ($$$1 \le d_1 \le d_2 \le 10^9$$$), and the city number $$$c$$$ where they are held ($$$1 \le c \le 10^9$$$) are written separated by a space. The input data is sorted in non-decreasing order of $$$d_1$$$.

Output

Output a single integer — the number of the first day on which Vasily is supposed to be simultaneously in two (or more) different cities. If there is no such day, then output 0.

Scoring

Solutions working for $$$N \le 1000$$$, $$$d_2 \le 1000$$$ will be scored out of 50 points.

Example
Input
3
1 7 5
2 4 5
3 5 2
Output
3
Note

Let's assume that all cities are located close to each other, so travel time is not considered in this problem.

Note for Python programmers: three numbers written separated by a space can be read as follows: 

d1, d2, c = map(int, input().split())