SP780 ARCHPLG - The Archipelago

Byteland is a country located in the Archipelago of Rectangular Islands. The archipelago consists of 1

In the first line t - the number of tests, then for each test: in next line n - the number of islands. Description of each island is as follows: ``` name w h [island dimensions] b - [number of terminals] [description of each terminal in a form:] name x y [name of a terminal and its coordinates] F [number of restricted areas F ``` All coordinates are nonnegative integers measured in BM according to upper left corner of an island. You can assume that any two restricted areas are disjoint. After the description of all islands all ferry connections are given (each connection is bi-directional). ``` m [number of connections] [description of each connection] NB1 NW1 NB2 NW2 time [name of a first terminal, its island, the second respectively and communiaction time] ... [description follows] ... NBS NWS NBC NWC [start and goal terminal for John] ```

For each test describe the shortest route for John from terminal NBS on NWS island to terminal NBC on NWC island in the following format: ``` case nr Y [nr - test number] T [travel time in BH] NBS NWS ... [consecutive terminals] ... NBC NWC [empty line] [consecutive tests] ``` If two consecutive terminals are located on the same island and John must take some walk you must give all middle point like in an example.