Message Routing

The International Standards Organization defined a Message Handling System (MHS) known as X.400. Within an MHS, a functional unit called the Message Transfer Agent (MTA) is responsible for routing messages.

Routing is driven by the components of a message's Originator/Recipient (O/R) name. For this problem an O/R name has four components, listed from widest to narrowest scope:

1. Country (C)
2. Administrative Management Domain (ADMD)
3. Private Management Domain (PRMD)
4. Organization Name (O)

Every MTA keeps its own routing table and uses it either to forward a message to the next MTA or to deliver the message locally.

Your task is to simulate a set of MTAs processing messages. Whenever a message arrives at (or is submitted to) an MTA, the MTA matches the message's O/R name against its routing table to decide where to send the message next. If the selected destination is the MTA itself, the message is delivered locally. Trace the path of each message through the MTAs.

How a routing table is used. Each routing-table entry names exactly one destination MTA together with four fields corresponding to the four O/R name components. A single MTA may appear in several entries. Scanning its routing table from top to bottom, the MTA selects the first entry whose four fields all match the message's four O/R name components; the message is then forwarded to the MTA named in that entry. A field may be a wildcard, written as an asterisk *, which matches any value in the corresponding O/R name component. A non-wildcard field matches only when it is exactly equal to the message's component.

Error handling.

• Circular routing. If a message arrives at an MTA that has already handled it earlier along its path, the MTA detects a routing loop, discards the message, and issues a non-delivery report.
• Unroutable. If an MTA has no routing-table entry that matches the message's O/R name, it cannot route the message; it discards the message and issues a routing-error report.

The input consists of a series of routing scenarios and ends at end of file.

Each scenario begins with a line containing a single integer $M$ ($1 \le M \le 10$), the number of MTAs in the scenario. The descriptions of the $M$ MTAs follow.

Each MTA description starts with a line containing the MTA name followed by an integer $I$ ($0 \le I \le 9$), the number of entries in that MTA's routing table. The next $I$ lines each describe one entry: the name of an adjacent MTA, followed by the four O/R name fields — Country, ADMD, PRMD, and Organization — in that order.

Every name (MTA names and O/R name components) is a string of 1 to 10 alphabetic characters with no embedded spaces. Any of the four O/R fields in a routing entry may instead be a single asterisk *, marking a wildcard. All fields on a line are separated by whitespace.

After the MTA descriptions, a line contains a single integer $N$ ($0 < N < 32768$), the number of messages to simulate. Each of the next $N$ lines describes one message: the name of the MTA where the message is submitted (one of the MTAs above), followed by the message's four O/R name components — Country, ADMD, PRMD, and Organization.

For each scenario, print a line Scenario # X, where $X$ is the scenario number starting from 1 and increasing by one for each subsequent scenario.

Then, for each of the $N$ messages in submission order, print one line consisting of the message number (starting from 1) immediately followed by exactly one of:

• -- delivered to MTA_NAME
• -- circular routing detected by MTA_NAME
• -- unable to route at MTA_NAME

where MTA_NAME is the name of the MTA that generated the report. Print each string exactly as shown, including the leading space, the dashes, and the spacing.

Separate consecutive scenarios with a single blank line. Do not print a blank line after the final scenario.