Median of Two Sorted Arrays

Problem statement

Two observatories maintain sorted lists of measurements. A researcher needs the median of the combined observations without spending time copying and sorting every value into a new list. Your task Compute the median of the union of the two sorted arrays, retaining duplicates. For an even total length, average the two central values. Target O(log(m+n)) time. Important details Either array may be empty, but together they contain at least one value. Negative values are allowed. Print one digit after the decimal point, including .0 for an integer result; avoid overflow while averaging. Worked example Measurements [1, 7] and [2, 4] combine to [1, 2, 4, 7]. The middle values are 2 and 4, so the median is 3.0.

Input format

First line: m n. Then m values of the first sorted array and n values of the second.

Output format

Print the median with exactly one digit after the decimal point.

Constraints

0 <= m, n <= 1000; 1 <= m+n <= 2000; -1000000 <= values <= 1000000.

Sample input

2 2
1 7
2 4

Sample output

3.0