Task

Compute the mutual information (MI) between a discrete event-type feature and a binary anomaly label.

MI = ∑_{e,y} p(e,y) · log₂( p(e,y) / (p(e) · p(y)) )

where the sum is over all (event_type, label) pairs with p(e,y) > 0.

Also compute the marginal entropy H(Y) = -∑_y p(y) · log₂(p(y)) and the conditional entropy H(Y|E) = H(Y) - MI.

Input

• Line 1: integer n — number of samples
• Lines 2 to n+1: event_type label (event_type is a string, label is 0 or 1)

Output

Three lines:

1. MI — mutual information
2. H_Y — marginal entropy of the label
3. H_Y_given_E — conditional entropy H(Y|E) = H(Y) - MI

Print all values with 10 significant figures ({:.10g}).

Example

Input:

8
E1 1
E1 1
E1 0
E2 0
E2 0
E2 0
E3 1
E3 0

Output:

0.3600730652
0.954434003
0.5943609378

Scaffolding

Submit a Python file defining:

def mutual_info(samples: list[tuple[str, int]]) -> tuple[float, float, float]:
    ...

Returns (MI, HY, HYgivenE).