There are k sensors, and each sensor reports a non-empty list of integer readings sorted in non-decreasing order. Find the smallest inclusive band [lo, hi] (with lo <= hi) such that every sensor has at least one reading r with lo <= r <= hi.
Minimize the band width hi - lo. If several bands achieve the minimum width, choose the one with the smallest lo. It is guaranteed that lo and hi can be chosen as actual readings.
Input format
Line 1: an integer k, the number of sensors.
Next k lines: each line starts with an integer L >= 1 (the number of readings for that sensor) followed by L non-decreasing integers.
Output format
Two integers lo and hi on one line, separated by a space: the endpoints of the smallest covering band.
Constraints
- 1 <= k <= 5000
- 1 <= L for each sensor
- The total number of readings is at most 100000.
- -1000000000 <= each reading <= 1000000000