С двух независимых космических зондов получены отсортированные по неубыванию массивы временных меток $A$ длины $n$ и $B$ длины $m$. Необходимо вычислить медиану объединённого отсортированного массива за асимптотическое время $O(\log(\min(n, m)))$.

Медиана объединённого массива длины $K = n + m$:

Входные данные

Выходные данные

Примеры

Пример 1

2
1 3
1
2

2.00000

Пример 2

2
1 2
2
3 4

2.50000