900. Solve Puzzle

1

Hard

"Can you Solve this Puzzle : "

Given two sorted arrays of size m and n, find the median of these two sorted arrays in logarithmic time.

Given two sorted arrays of size m and n, find the median of these two sorted arrays in logarithmic time.

Input Format

First-line contains two integers n and m size of two arrays

Second-line contains the n element of array1 Third and last line contains m element of array2

Second-line contains the n element of array1 Third and last line contains m element 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