Paint Line Through the Poster Wall

A wall is covered by rectangular panels. Panel i is panels[i] = [bottom, height, width]: its lower edge is at height bottom, it is height tall and width wide. Panels may overlap; every panel's full area counts, even where it is covered by another.

A painter will paint every panel blue below a horizontal line at height y. Find the lowest y for which the blue area is at least half of the total panel area. Return it as a reduced fraction [p, q] with q > 0 and gcd(p, q) = 1.

Examples

Input:  panels = [[0, 2, 3], [1, 2, 1]]
Output: [5, 4]
Explanation: total area 8. At y = 1 the blue area is 3; above that it grows by 4 per unit
(both panels), so it reaches 4 at y = 5/4.

Input:  panels = [[0, 1, 2], [5, 1, 2]]
Output: [1, 1]
Explanation: blue area is half at every y from 1 to 5; the lowest is 1.

Constraints

• 1 <= len(panels) <= 10**4
• 0 <= bottom <= 10**9, 1 <= height <= 10**9, 1 <= width <= 10**4
• The heights span up to 2 * 10**9, so stepping through every whole height is too slow.

Goals

• Binary search a monotone quantity over integer breakpoints, then solve one linear piece exactly
• Return an exact real-valued answer as a fraction instead of an approximation