A binary tree of stock-portfolio returns is given in level-order form (a single line of space-separated tokens, null marking a missing child; every non-null node contributes exactly two following tokens for its children). The tree always has at least one node.
For any node, define its subtree's average as (sum of all values in its subtree) divided by (the number of nodes in its subtree). Find the maximum such average over every subtree of the tree (including single-node subtrees and the whole tree), and print it as an exact fraction p/q in lowest terms, with q > 0 (print 0/1 if the maximum average is exactly zero).
Input format
Line 1: space-separated level-order tokens describing the binary tree (integers and the token null). The tree has at least 1 node.
Output format
A single line of the form p/q: the maximum subtree average, as a reduced fraction with a positive denominator.
Constraints
- 1 <= number of nodes <= 300
- Each node value is an integer with -1000 <= value <= 1000