Task

Given HDFS log events as (BlockId, EventTemplate) pairs, compute the Shannon entropy of the event-template distribution for each block.

Shannon entropy: H = -∑ pi · log₂(pi), where p_i = (count of event type i) / (total events in block).

A block with all events of one type has H = 0. A block with k equally-frequent event types has H = log₂(k).

Input

• Line 1: integer n
• Lines 2 to n+1: block_id event_template

Output

For each block in ascending order of block_id, print one line: block_id entropy

Print entropy with 10 significant figures (use {:.10g} format).

Example

Input:

4
1 E1
1 E2
2 E3
2 E3

Output:

1 1
2 0

Notes

• Track M: pure Python only (no NumPy needed). The formula is exact floating-point arithmetic via math.log2.
• Anomaly detection context: entropy of event-template counts per BlockId is a useful feature — anomalous HDFS blocks tend to exhibit more uniform or unusual event-type distributions.

Scaffolding

Submit a Python file defining:

def entropy_features(events: list[tuple[int, str]]) -> list[tuple[int, float]]:
    ...

Returns list of (blockid, entropy) sorted by blockid ascending.