Reţeaua de tramvaie din Bucureşti este formată din N staţii numerotate distinct de la 1 la N. O rută este formată dintr-o succesiune de staţii. Există T rute pe care circulă fără întreruperi un număr nelimitat de tramvaie la interval de 1 minut. Pe orice rută tramvaiele circulă în ambele direcţii.
Domnişoara Andreea este din Timişoara. Ea tocmai a ajuns în Bucureşti şi se află în staţia S. Andreea are o listă de P destinaţii, iar pentru fiecare destinaţie Di (0 < i ≤ P) ar vrea să ştie care este timpul minim în care poate ajunge de la S la Di folosind tramvaiele ca mijloace de transport. Ea poate coborî în oricare staţie de pe ruta tramvaiului în care se află şi se poate urca în oricare alt tramvai care trece prin staţia respectivă. Deoarece tramvaiele vin la intervale atât de scurte, la fiecare minut va fi un tramvai în staţie, deci vom considera că o astfel de transbordare se realizează atât de repede încât putem neglija timpul necesar ei, cât şi timpul de staţionare a tramvaielor. Dar pentru că Bucureştiul e cam mare şi Andreea nu prea se descurcă, vă cere ajutorul.
Cerinţă
Determinaţi timpii minimi necesari pentru a ajunge din staţia S la fiecare destinaţie Di (0 < i ≤ P).
Date de intrare
Pe prima linie din fişierul trmv.in se găsesc 4 numere naturale N T S P cu semnificaţia din enunţ. Următoarele T linii descriu rutele de tramvai, câte o rută pe o linie. O linie care descrie o rută conţine un număr natural L urmat de 2L-1 numere naturale k1, t1, k2, t2,…,kL-1, tL-1, kL. Fiecare triplet (ki, ti, ki+1) 1≤i<L indică faptul că pe ruta descrisă tramvaiele vor parcurge distanţa dintre staţiile ki şi ki+1 în ti minute. Nu uitaţi că pe orice rută tramvaiele circulă în ambele direcţii (atât de la k1 la kL trecând în ordine prin k2, k3,...,kL-1 cât şi de la kL la k1 trecând prin kL-1,kL-2,...,k2 în această ordine). Ultima linie din fişier conţine P numere naturale cuprinse între 1 şi N reprezentând cele P destinaţii pentru care va trebui să calculaţi timpul minim. Valorile scrise pe aceeaşi linie sunt separate prin spaţii.
Date de ieşire
Fişierul de ieşire trmv.out va conţine o singură linie pe care se vor afişa P numere întregi separate prin câte un singur spaţiu reprezentând timpul minim determinat pentru fiecare destinaţie, în ordinea din fişierul de intrare. Pentru destinaţiile la care nu se poate ajunge se va afişa valoarea -1.
Restricţii
1 ≤ P ≤ N ≤ 1 000 000
1 ≤ T, L ≤ 1000
1 ≤ ti < 16
Pentru 30% din punctaj toţi timpii vor fi de 1 minut
Fiecare rută de tramvai are propria linie atât pe un sens cât şi pe celălalt, astfel că nu există riscul ca două tramvaie să se ciocnească.
Andreea este deja în staţia 1, deci timpul minim până la această staţie este 0. Timpul minim până la staţia 6 se obtine mergand cu tramvaiul pe prima rută de la 1 până la 2, apoi pe ruta 3 de la 2 până la 3, trecând prin 4, după care se va folosi ruta 5 între 3 şi 7, iar în final ruta 4 între 7 şi 6. Timpul total este de 2+1+1+2+3=9 minute. Nu există nicio modalitate de a ajunge în staţia 5, deci ultimul număr afişat este -1.