MBone

MBone is short for Multicast Backbone: a virtual network built on top of the Internet Protocol. Alongside connection-oriented delivery to a single receiver (unicast) and delivery from one sender to every host in a network (broadcast), it offers multicast — delivery to exactly the hosts that have joined a given multicast group. Every member of a group can both send data to the group and receive data from it.

Your task is to simulate a simplified MBone.

In this model the network is made of multicast routers and hosts; every host belongs to exactly one router. A router together with the hosts that belong to it is called an island. Routers are linked by tunnels, one-way communication channels: a packet sent into one end of a tunnel comes out the other end.

• To join a multicast group, a host sends a request to its own router naming the group. From then on it receives every packet sent to that group.
• To send a packet to a group, a host hands the packet to the router of its island. Every router that receives a packet duplicates it, forwards a copy through each of its outgoing tunnels, and then delivers a copy to every host on its island that has joined the packet's group (including the sender itself, if it is a member).

A packet carries an integer TTL (Time To Live) that limits how far it spreads. When a packet is forwarded through a tunnel, its TTL is reduced by that tunnel's threshold (an integer). A packet is not forwarded through a tunnel when its current TTL is smaller than the tunnel's threshold.

If a host would receive several copies of the same packet through different paths, it keeps only the copy with the highest remaining TTL (the one that reached it along the shortest path).

The input contains several network descriptions. Each description has two parts: first the topology, then the activity.

• The first line of a description is an integer m (1 ≤ m ≤ 10), the number of islands. A line containing 0 marks the end of the input.

• The next lines describe the m islands. Each island begins with a line

  <router name> <count>

  where the router name is a string of at most 20 non-blank characters and count is the number of description lines that follow. Each of those lines is one of:

  • H <host address> — a host on this island.
  • T <threshold> <destination router name> — an outgoing tunnel to another router (always different from the current one).

  Both <host address> and <threshold> are positive integers.

• After the islands comes a line with a single integer (at most 1000): the number of activity lines that follow. Each activity line is one of:

  • J <host address> <group address> — the host joins the group.
  • L <host address> <group address> — the host leaves the group.
  • S <host address> <group address> <packet ID> <TTL> — the host sends a packet to the group.

  <group address>, <packet ID> and <TTL> are positive integers, and every TTL is at most 1000.

Within one scenario all router names, all host addresses and all packet IDs are unique. At any moment there are at most 50 hosts, at most 100 tunnels and at most 20 active groups (groups with at least one member). No host ever leaves a group it is not in or joins a group it is already in.

For each network, print every packet received by its hosts.

Begin with the line Network #k, where k is the number of the network (the first is 1). Then print one line per received packet in the format

<host address> <packet ID> <remaining TTL>

with the three fields separated by single spaces. If a host received several copies of one packet, print only the copy with the highest remaining TTL. Sort the lines in ascending order, first by host address and then by packet ID.

Separate the outputs of consecutive networks with a single blank line.