Task

Compute the information gain of a binary split given the class-count distributions in the parent node and the two child nodes. Information gain = H(parent) - (nleft/nparent)H(left) - (n_right/n_parent)H(right), where H is the Shannon entropy H = -sumc pc * log2(p_c) over class proportions. The counts for each node may include more than two classes.

Input

• Line 1: c_0 c_1 ... — class counts in the parent node (space-separated)
• Line 2: c_0 c_1 ... — class counts in the left child node
• Line 3: c_0 c_1 ... — class counts in the right child node

Output

Print the information gain as a single float with up to 10 significant digits.

Example

Input:

5 5
4 1
1 4

Output:

0.2780719051

Scaffolding

Submit a Python file defining:

def information_gain(parent_counts: list[int], left_counts: list[int],
                     right_counts: list[int]) -> float:
    ...

Receives three lists of class counts (parent, left child, right child); returns the information gain as a float.