该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

You are supposed to implement an auto taxi management system: for each customer who is ordering a service, send a command to an auto taxi that can take the shortest time to reach the customer. The rules are:

• One can only get a taxi and set one's destination at some pickup spots.
• Any taxi can accept a command at any time after it shows up in the system.
• Any taxi that is carrying passengers on the road must first send its passengers to their destination, before it can carry the next command;
• If there is no more command, a taxi will stay at the destination of its last passenger and wait;
• If there are many taxis that can reach the customer at the same shortest time, the command will be sent to the one without any passenger on board. If there is still a tie (that is, if all the taxis are carrying passengers, or several taxis are waiting), then pick the one with the smallest index, which is guaranteed to be unique.

Note: If a taxi arrives a destination at the same time as a customer submits an order, the taxi is considered empty, without any passenger on board.

输入格式

Each input file contains one test case. For each case, first a map is given in the following format:

In the first line, two positive integers are given: $N_v$ ($\le 1000$) and $N_e$, which are the total number of pickup spots (hence the spots are indexed from 1 to $N_v$) and the number of streets connecting them.

Then $N_e$ lines follow, each describes a street by

spot1 spot2 time

where spot1 and spot2 are the indices of the two ends of the street, and time is the positive integer time taken to pass this street, in minutes. It is assumed that no street will take more than 100 minutes to pass. And it is guaranteed that no duplicated information is given for any of the streets.

The next block is for the auto taxis.

In the first line, a positive integer $M$ ($\le 1000$) is given. Then $M$ lines follow. The $i$-th line describes the status of the $i$-th taxi (hence the taxis are indexed from 1 to $M$) in the fomat:

pickup_time pickup_spot destination

means that the taxi has picked up someone from pickup_spot at pickup_time, and is driving to destination. Here pickup_time is in the form hh:mm, where hh is in [00, 23] and mm is in [00, 59]. When pickup_spot is the same as destination, it means that the taxi has no passenger and is waiting for the next command at destination.

The last block is for customer orders. In the first line, a positive integer $K$ ($\le 1000$) is given. Then $K$ lines follow, each describes an order in the fomat:

order_time pickup_spot destination

means that one has submitted an order of taxi at order_time (same format as pickup_time), going from pickup_spot to destination. It is guaranteed that:

• the orders are given in increasing order of order_time;
• all the order_time's are after the latest pickup_time given in the taxis block, and are within the same day;
• pickup_spot is never the same as destination;
• all the pickup_spot's are connected to each other directly or indirectly; and
• there is no one-way street road.

输出格式

For each order, output in a line the index of the taxi to be sent to the customer, following the rules given by the problem description.

样例

7 12
1 2 50
1 3 10
1 4 20
1 5 30
1 6 20
1 7 60
2 3 20
2 4 10
3 5 20
4 6 60
5 7 100
6 7 30
4
07:20 2 1
07:10 4 3
06:40 7 3
07:35 4 4
5
07:40 1 7
07:50 6 3
08:00 7 6
08:10 3 4
08:35 6 5

2
1
2
3
1

限制

对于所有的测试用例,限制为 2000 ms, 64 MB