Smallest Range Covering K Lists

lists holds k lists of numbers, each sorted in increasing order and non-empty. Find the smallest range [lo, hi] that contains at least one number from every list. A range [a, b] is smaller than [c, d] if b - a < d - c, or if the lengths are equal and a < c. Return [lo, hi].

For [[4, 10, 15, 24, 26], [0, 9, 12, 20], [5, 18, 22, 30]] the answer is [20, 24].

Examples

Example 1

Input:

smallest_range([[4, 10, 15, 24, 26], [0, 9, 12, 20], [5, 18, 22, 30]])

Output:

[20, 24]

Example 2

Input:

smallest_range([[1, 2, 3], [1, 2, 3], [1, 2, 3]])

Output:

[1, 1]

Constraints

• 1 <= k <= 3500
• 1 <= total number of values <= 100000
• -10**5 <= value <= 10**5