Shipment Routing Capacity Check

In this problem, you are given a network of hubs and a list of shipments scheduled on specific days. Each shipment starts at one hub and ends at another. Every shipment contributes to the load of both the start and end hub on the day it is scheduled. Given the maximum capacity for a hub in a single day, determine whether it is possible to route all shipments without any hub exceeding its capacity.

Formally, let there be (H) hubs and a hub capacity (C). You are given (N) shipments, where each shipment is represented by a triple ((S, E, D)) indicating that a shipment goes from hub (S) to hub (E) on day (D). For any given day, if for any hub the total number of shipments (as a sender or receiver) exceeds (C), then the shipments cannot be routed without breaking the capacity constraint and the answer should be "Impossible". Otherwise, output "Possible".

inputFormat

The input is read from standard input (stdin) and consists of multiple lines. The first line contains three integers: (H) (the number of hubs), (C) (the maximum capacity per hub per day), and (N) (the number of shipments). This is followed by (N) lines, each containing three integers (S), (E), and (D), representing a shipment from hub (S) to hub (E) on day (D).

outputFormat

Print a single line to standard output (stdout) containing either "Possible" if all shipments can be routed within the hub capacities for all days, or "Impossible" otherwise.## sample

3 2 5
1 2 1
2 3 1
1 3 2
3 1 1
2 1 3

Possible