POLSKI SPOJ

Bajtlandia to kraj położony w Archipelagu Wysp Prostokątnych. Na archipelag składa się 1 ≤ n ≤ 10³ wysp, z których każda ma kształt prostokąta, co znacznie ułatwia pracę Bajtlandzkich kartografów.

Komunikację pomiędzy wyspami umożliwia mieszkańcom rozbudowana sieć połączeń promowych. Na brzegach każdej wyspy znajduje się 1 ≤ b ≤ 10 baz promowych, z każdej bazy można popłynąć w przynajmniej jednym kierunku, to znaczy do bazy położonej na innej wyspie. Wiadomo, że łączna liczba wszystkich połączeń wynosi 0 ≤ m ≤ 10⁵.

Bajtlandzkie wyspy nie są ani rozległe, ani bardzo urodzajne, dlatego każdy (prostokątny) skrawek nadającej się do tego ziemi jest przeznaczony pod uprawy. Bajtlandczycy mają poszanowanie dla darów natury i cudzej własności dlatego nigdy, ale to nigdy nie wchodzą na te skądinąd pilnie strzeżone i ogrodzone drutem kolczastym tereny. Pozostałe obszary są ogólnodostępne, a bajtlandzkie prawo gwarantuje swobodny do nich dostęp. Mieszkańcy, choć dzieje się to rzadko, poruszają się po nich pieszo. Bajtlandczycy w ogóle rzadko podróżują. Dlatego w całym archipelagu nie ma ani kawałka drogi, ani jakiegokolwiek pojazdu lądowego.

Jan jest dość nietypowym obywatelem tego wyspiarskiego kraju. Jako agent ubezpieczeniowy porusza się on po całym archipelagu, jeśli tylko otrzyma wiadomość od potencjalnego klienta. Jest to osoba bardzo zajęta i rzadko znajduje czas na przesiadywanie nad brzegiem morza i gry planszowe, które są ulubioną rozrywką Bajtlandczyków.

Być może jest ktoś, kto może ulżyć Janowi w jego ciężkiej i często niewdzięcznej pracy tak, by miał więcej wolnego czasu?

Zadanie

Znajdź najkrótszą, pod względem czasu podróży, drogę dla Jana korzystając z połączeń promowych oraz pieszych szlaków po wyspach. Przyjmij, że po lądzie Jan porusza się ze średnią prędkością 1 blindry (bajtlandzka jednostka odległości) na blingundrę (bajtlandzka jednostka czasu). Promy odpływają zawsze o pełnych blingundrach, dlatego czas przejścia pieszo przez wyspę należy zaokrąglić w górę do pełnych blingundr.

Input

W pierwszej linii t - liczba testów, dalej dane dla każdego testu. W kolejnej linii n - liczba wysp po czym opis każdej wyspy. Wszystkie współrzędne są nieujemnymi liczbami całkowitymi wyrażonymi w blindrach względem rogu wyspy.

nazwa_wyspy
w h [rozmiary szerokość i długość]
b - [liczba baz promowych na wyspie]
[dalej opis każdej bazy:]
nazwa x y [unikalna na wyspie nazwa bazy i jej  współrzędne]
F [liczba obszarów zabronionych na wyspie, F ≤ 20]
xl, yd, xr, yu [współrzędne dwóch wierzchołków kolejnego obszaru zabronionego,
0 ≤ xl < xr ≤ 250 0 ≤ yd < yu ≤ 250.]

Można przyjąć, że żadne dwa obszary nie stykają się ze sobą.

Po wszystkich danych dotyczących wysp, mamy kolejno dane o połączeniach promowych (każde połączenie jest dwukierunkowe):

m  [liczba połączeń]
[Teraz opis wszystkich połączeń]
NB1 NW1 NB2 NW2 time [Nazwa bazy i nazwa wyspy startowej i docelowej
oraz czas połączenia między nimi]
...
[tu kolejne połączenia]
...
NBS NWS NBC NWC [startowa i docelowa baza Jana]

Output

Dla każdego testu należy wypisać najkrótszą drogę z bazy Nazwa1 na wyspie Wyspa1 do bazy Nazwa2 na wyspie Wyspa2 w następującym formacie:

case nr Y [nr - kolejny numer testu, litera N, jeśli brak rozwiązania]
T [Czas podróży w blingundrach]
Nazwa1 Wyspa1
...
[tu bazy pośrednie]
...
Nazwa2 Wyspa2
[pusta linia]
[odpowiedzi dla kolejnych testów]

Jeśli dwie kolejne stacje pośrednie leżą na jednej wyspie i należy przejść pieszo z jednej bazy do drugiej, to należy podać wszystkie wierzchołki łamanej po której Jan powinien się poruszać we współrzędnych danej wyspy tak jak w przykładzie.

Example

Input:
1
3
W1
8 7
2
Lindos 4 0
Kamejros 4 7
3
2 1 6 2
2 3 6 4 
2 5 6 6 
W2
14 12
2
Malia 14 1
Knossos 1 12
5
2 6 10 10
11 1 12 6
8 1 10 5
11 7 12 9
3 2 5 4
W3 
1 1
1
Korkyra 0 0
0
2
Kamejros W1 Knossos W2 100
Malia W2 Korkyra W3 100
Korkyra W3 Lindos W1

Poniżej przykład prawidłowej odpowiedzi

Output:
case 1 Y
230
Korkyra W3
Malia W2
12 6
11 7
10 10
Knossos W2
Kamejros W1
2 6
2 1
Lindos W1

Podpowiedź

Testów jest 100. W pierwszych 20 testach wysp jest mało i nie występują obszary zabronione. Dodatkowo w pierwszych 10 testach na każdej wyspie jest tylko 1 baza. Każdy przypadek ma rozwiązanie.