The median is the middle value in an ordered integer list. If the size of the list is even, the median is the mean of the two middle values.

Implement the MedianFinder class:

• addNum(num) — adds integer num to the data structure.
• findMedian() — returns the median of all elements so far.

Answers within 10⁻⁵ of the actual answer will be accepted.

Example:

Input:
addNum 1
addNum 2
findMedian
addNum 3
findMedian

Output:
1.50000
2.00000

Constraints:

• -10⁵ ≤ num ≤ 10⁵
• At most 5 × 10⁴ calls total.
• findMedian is always called with at least one number added.

Input format: One command per line. addNum X adds X. findMedian prints the current median.

Output format: Print a result line only for findMedian (5 decimal places).