Background

NOI1998 D2T2.

Problem Description

Computer networks are a hot topic in modern technology development, and transmission performance is a main performance indicator of computer networks. The SERKOI network development team designed a network called SERNET, and hopes to develop a simulation program to simulate data transmission in this network, so as to compute the network's transmission performance.

The SERNET network consists of servers and the network transmission links connecting them. Each server is identified by a server address, and each transmission link is bidirectional. During network transmission, all data to be transmitted is split into multiple packets of the same size, and transmission is done packet by packet. A packet needs some transmission time to travel on a link, and different links have different transmission times. The time a server spends processing data is very small compared with transmission time and can be ignored. Besides the actual data, each packet also contains the following identification information:

• Packet ID.
• Source server address.
• Destination server address.

The function of network transmission is to send packets from the source server to the destination server. For each packet, the specific transmission scheme is:

The source server copies the packet into several copies and sends the packet to all servers directly connected to it. After a server receives a packet, if the packet satisfies any of the following conditions:

• The packet's source server address is the same as this server's address.
• The packet's destination server address is the same as this server's address.
• This server has already forwarded a packet with the same packet ID.

then it accepts the packet; otherwise, the server copies it into several copies and forwards the packet to all servers directly connected to it. Here, “connected” means there is a network transmission link directly connecting the two servers.

Now you need to write a program to simulate packet transmission in the SERNET network.

Input Format

The first line of the input file contains a positive integer $N$ ($N<100$), representing the number of servers in SERNET.

The second line contains $N$ distinct positive integers not exceeding $100$, representing the address of each server.

The third line contains a positive integer $M$, representing the number of transmission links in SERNET.

Each of the next $M$ lines contains three positive integers: “the addresses of the two servers connected by a transmission link” and “the transmission time of this link”. The transmission time is a positive integer not exceeding $100$.

The next line contains a positive integer $K$ ($K<10000$), representing the number of packets in SERNET.

Each of the following $K$ lines describes one packet in the format:

• packet ID start sending time source server address destination server address.

The packet IDs are distinct positive integers less than $100000$.

The last line of the input file contains a positive integer $T$ ($T<10000$), where $T$ is the output time.

In the input file, adjacent items on the same line are separated by one or more spaces.

Output Format

The first line of the output file contains an integer $P$, representing the number of packets that are still being transmitted in the network after time $T$ (packets with the same ID are considered the same packet).

4
57 42 10 93
4
57 42 6
42 93 5
42 10 2
10 93 10
2
433 10 57 10
5678 11 42 93
23

1

Hint

[Constraints Explanation]

• Subtask 0 uses the official CCF testdata and is relatively easy.
• Subtask 1 uses community-made testdata.

[Conventions]

• All time quantities in this problem use the same unit.
• On the same transmission link, any number of packets can be transmitted at the same time.

Translated by ChatGPT 5