Shift Scheduling Problem

You are given a list of workers with their preferred shifts and a set of shifts with required number of workers. The task is to assign each worker to one of their preferred shifts such that all shifts are fully staffed. If it is impossible to meet the shift requirements with the given preferences, output Impossible.

More formally, let \(n\) be the number of workers and \(m\) be the number of shifts. Each worker \(i\) has a list of preferred shifts \(P_i\). Each shift \(j\) requires exactly \(r_j\) workers. The assignment must satisfy that every worker is assigned to exactly one shift from their preferences and for each shift \(j\), the number of workers assigned equals \(r_j\). If any worker cannot be assigned a valid shift or if any shift does not meet its requirement, the answer is \(\text{Impossible}\).

inputFormat

The first line contains two integers \(n\) and \(m\) representing the number of workers and the number of shifts respectively. The next \(n\) lines each contain a worker's name followed by one or more integers indicating their preferred shift indices. The following \(m\) lines each contain two integers: a shift index and the required number of workers for that shift.

Input is provided via stdin.

outputFormat

If a valid assignment is possible, output each assignment on a separate line in the format worker_name: shift_index. The assignments should be listed in increasing order of shift indices. If there are multiple workers assigned to the same shift, their order can be as assigned. If a valid assignment is not possible, output a single line containing Impossible.

Output to stdout.

## sample

4 3
Alice 1 2
Bob 2 3
Charlie 1
David 3
1 2
2 1
3 1

Alice: 1
Charlie: 1
Bob: 2
David: 3

</p>