Task

Build a count matrix from HDFS log events. Given a list of log entries and a list of event template names, produce a matrix where:

• Each row corresponds to a BlockId (sorted ascending)
• Each column corresponds to an event template (in the given order)
• Each cell contains the count of that event template for that block

Input

• Line 1: integer e — number of distinct event templates
• Line 2: e space-separated event template names (the column order)
• Line 3: integer n — number of log entries
• Lines 4 to n+3: block_id event_template

Output

For each block in ascending order of blockid, print one line: block_id c1 c2 ... ce where ci is the count of template i for that block.

Example

Input:

3
E1 E2 E3
7
1 E1
1 E2
1 E1
2 E3
2 E1
3 E2
3 E2

Output:

1 2 1 0
2 1 0 1
3 0 2 0

Scaffolding

Submit a Python file defining:

def event_count_matrix(templates: list[str], events: list[tuple[int, str]]) -> list[tuple[int, list[int]]]:
    ...

Returns list of (blockid, counts) sorted by blockid ascending, where counts[i] is the count of templates[i].