Nearest marker pair: hints, no solution

Two tracks in a mixing project each carry a list of marker times, in milliseconds, in ascending order. The producer wants to line up one marker from the first track with one marker from the second so that they nearly coincide.

Return the smallest absolute difference between any marker on the first track and any marker on the second track. Both lists have at least one marker, a time can be repeated within a list, and the result is 0 when the tracks share a marker time.

Examples

Input

first = [1, 5, 9], second = [6, 12]

Output

1

Note

Markers 5 and 6 differ by 1, and no other pair is closer.

Input

first = [2, 4, 8], second = [4, 10]

Output

0

Note

Both tracks have a marker at 4, so the difference is 0.

Input

first = [3], second = [10]

Output

7

Note

With one marker each, the answer is their difference.

Constraints

• 1 <= first.length, second.length <= 125000
• 0 <= time <= 1000000, each list is non-decreasing
• Return a non-negative integer

Hint 1: a nudge

Suppose you compare one marker from each track. What does that tell you about which marker is worth advancing?

Unlock the full hints and timed practice with a pass

The second and third hints and the timed, runner-checked practice are part of a pass.

See pricing