7. Osobná doprava

Táto úloha má tak dlhé zadanie, že by potrebovala mínus pätnásť riadkov rozprávky.

Máme krajinu a v krajine rozmiestnených niekoľko zastávok. Zastávky majú mená: reťazce 1 až 10 malých písmen anglickej abecedy. Medzi \(d\) dvojicami zastávok sa dá priamo cestovať. Pre takéto dvojice zastávok máme zadanú vzdialenosť v metroch. (Vzdialenosť je rovnaká oboma smermi.)

V našej krajine existuje \(s\) jednosmerných spojení. Každé spojenie postupne navštívi dve alebo viac zastávok. Popis spojenia obsahuje okrem zoznamu zastávok ešte tri parametre: jeho rýchlosť \(v_i\) (v metroch za sekundu), jeho periódu \(p_i\) (v sekundách) a jeho offset \(o_i\) (tiež v sekundách). Čas potrebný na presun medzi dvoma zastávkami si vieme vypočítať tak, že vzdialenosť medzi nimi vydelíme rýchlosťou a výsledok zaokrúhlime nahor na celé sekundy. Význam offsetu a periódy je nasledovný: Po trase spojenia už od nepamäti každých \(p_i\) sekúnd vyráža zo začiatočnej zastávky nový spoj. Najbližšie sa tak stane o \(o_i\) sekúnd odteraz.

Všimnite si, že pre jednoduchosť predpokladáme, že sa perióda nemení počas dňa. A taktiež sme zanedbali čas státia na zastávke: všetky naše spoje na zastávkach stoja 0 sekúnd, nastupuje a vystupuje sa za jazdy :)

Medzi spojeniami vieme na zastávkach ľubovoľne prestupovať. Na prestup nám tiež stačí nulový čas. Ak teda zastávkou prechádzajú v tom istom okamihu dva rôzne spoje, stíhame prestúpiť z jedného na druhý. Na zastávkach samozrejme môžeme na prestup aj ľubovoľne dlho čakať.

Úloha

Daný je popis siete zastávok a spojení medzi nimi. Následne nasleduje niekoľko otázok. Každá otázka je tvorená dvomi menami zastávok: odkiaľ a kam chceme ísť. Vašou úlohou je vypočítať, či sa to dá, a ak áno, v akom najkratšom čase. Presnejšie, ak sme v čase 0 na zastávke, odkiaľ ideme, v akom najskoršom čase vieme byť na zastávke, kam ideme?

Formát vstupu

V prvom riadku vstupu je číslo \(d\), udávajúce počet dvojíc zastávok, medzi ktorými sa dá priamo cestovať. V každom z ďalších \(d\) riadkov vstupu je popis jednej dvojice zastávok. Tento je uvedený vo formáte “meno1 meno2 vzdialenost”.

V nasledujúcom riadku je číslo \(s\), udávajúce počet spojení. V každom z nasledujúcich \(s\) riadkov je popis jedného spojenia. Tento je uvedený vo formáte “\(v_i\) \(p_i\) \(o_i\) \(z_i\) zastavka_1 ... zastavka_\(z_i\)”. Významy \(v_i\), \(p_i\) a \(o_i\) sú uvedené vyššie, číslo \(z_i\geq 2\) udáva počet zastávok obsluhovaných spojením. Zastávky sú navzájom rôzne a pre každú dvojicu po sebe idúcich zastávok sme na vstupe mali uvedenú ich vzdialenosť.

V nasledujúcom riadku je číslo \(q\leq 10\), udávajúce počet otázok. V každom z ďalších, posledných \(q\) riadkov vstupu je popis jednej otázky. Tento je uvedený vo formáte “odkial kam”, pričom odkial a kam sú platné mená dvoch rôznych zastávok.

 Obmedzenia

Vo všetkých vstupoch platí \(d\leq 300\,000\), ale v približne polovici vstupov je \(d\) výrazne menšie. Rôznych zastávok bude nanajvýš \(100\,000\).

Všetky vzdialenosti medzi zastávkami, rýchlosti a periódy sú kladné celé čísla neprevyšujúce \(100\,000\). Pre offsety platí \(0\leq o_i < p_i\).

Súčet všetkých \(z_i\) (teda počtov zastávok jednotlivých spojení) neprekročí \(300\,000\). Vo vstupoch s malým počtom zastávok bude aj počet spojení malý.

Optimálna cesta (ak nejaká existuje) vždy trvá menej ako 20 dní. Všetky potrebné výpočty by sa vám teda mali zmestiť do bežných celočíselných premenných.

Formát výstupu

Pre každú otázku uveďte jeden riadok a v ňom text “neda sa” ak sa z daného začiatku do daného cieľa nedá dostať, resp. text “?d ?h ?m ?s”, kde namiesto otáznikov uveďte najmenší možný počet dní, hodín, minút a sekúnd, po ktorom vieme byť v cieli cesty.

Príklad

Input:

7
skladka smetisko 350
kontajner smetisko 299
dub javor 123
javor breza 234
dub breza 45678
breza lipa 1000
topol breza 50010
6
15 600 47 3 skladka smetisko kontajner
23 10 0 3 dub breza javor
1 1234 5 4 dub javor breza lipa
4 350 35 3 dub javor breza
100 1 0 2 javor dub
10 50 0 3 topol breza lipa
3
skladka kontajner
kontajner skladka
dub lipa

Output:

0d 0h 1m 31s
neda sa
0d 0h 4m 11s

Prvé spojenie má rýchlosť \(v_i=15\) (bežná MHD), periódu \(p_i=600\) (ide raz za 10 minút) a offset \(o_i=47\). Premáva na trase skladka – (350 m) – smetisko – (299 m) – kontajner. Vzdialenosť medzi skládkou a smetiskom prekonajú spoje tejto linky za 24 sekúnd, vzdialenosť medzi smetiskom a kontajnerom za 20. Najbližšie tri spoje po tejto trati odídu od skládky o 47, 647 a 1247 sekúnd odteraz, prejdú okolo smetiska o 71, 671 a 1271 sekúnd odteraz, a svoju cestu ukončia pri kontajneri o 91, 691 a 1291 sekúnd odteraz. Ak pôjdeme prvým z nich, dostaneme sa teda ku kontajneru o 1 minútu a 31 sekúnd od začiatku.

Pozrime sa teraz na poslednú otázku: ako sa dostať od dubu k lipe?

Ako prvé odchádza už v čase 0 spojenie, ktoré rýchlosťou 23 smeruje k breze a odtiaľ k javoru. Síce by sme sa ním mohli odviezť k breze, to ale nie je veľmi dobrý nápad – prišli by sme tam až po 1986 sekundách, a ešte by sme sa museli odtiaľ dostať k lipe.

Ide nám aj priama linka okolo javora a brezy k lipe, ani tou však nie je dobrý nápad ísť. Najbližší spoj síce ide už o 5 sekúnd, je však pomalý: potrvá mu to 123 sekúnd k javoru, ďalších 234 ku breze a ďalších 1000 k lipe. Do cieľa by sme teda dorazili až po 1362 sekundách.

Najlepšie riešenie vyzerá nasledovne: Na štarte počkám 35 sekúnd, potom nasadnem na spoj idúci rýchlosťou 4 okolo javora k breze. Ten ma za 31 sekúnd privezie k javoru a za ďalších 59 k breze. Tam vystúpim. Je práve 125 sekúnd od začiatku. O ďalších 26 sekúnd, teda v čase 151, pôjde okolo brezy spoj na linke topoľ-breza-lipa. (Všimnite si, že tento spoj vyrazil na svoju cestu výrazne skôr ako my.) Ten ma za 100 sekúnd prevezie od brezy k lipe. V cieli som teda po 251 sekundách.