507. Crack Enigma

0

Hard

"Can you Crack this Enigma: "

Given two arrays of size m and n, both sorted in ascending order, your task is to find the median of these two arrays in logarithmic time complexity.

Given two arrays of size m and n, both sorted in ascending order, your task is to find the median of these two arrays in logarithmic time complexity.

Input Format

The first line contains two integers n and m, representing the sizes of the two arrays.

The second line contains n space-separated integers, representing the elements of array1.

The third and last line contains m space-separated integers, representing the elements of array2.

The second line contains n space-separated integers, representing the elements of array1.

The third and last line contains m space-separated integers, representing the elements of array2.

Output Format

A double value representing the median of the arrays a and b.

Example

Input

4 4
1 3 4 9
2 5 6 8

Output

4.5

Constraints

0 <= m <= 1000

0 <= n <= 1000

1 <= m + n <= 2000

-10

0 <= n <= 1000

1 <= m + n <= 2000

-10

^{6}<= nums1[i], nums2[i] <= 10^{6}Loading...

View Submissions

Console