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 D_i (0 < i ≤ P) ar vrea să ştie care este timpul minim în care poate ajunge de la S la D_i 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 D_i (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 k₁, t₁, k₂, t₂,…,k_L-1, t_L-1, k_L. Fiecare triplet (k_i, t_i, k_i+1) 1≤i<L indică faptul că pe ruta descrisă tramvaiele vor parcurge distanţa dintre staţiile k_i şi k_i+1 în t_i minute. Nu uitaţi că pe orice rută tramvaiele circulă în ambele direcţii (atât de la k₁ la k_L trecând în ordine prin k₂, k₃,...,k_L-1 cât şi de la k_L la k₁ trecând prin k_L-1,k_L-2,...,k₂ î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 ≤ t_i < 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ă.

Exemple

trmv.in	trmv.out	Explicaţie
7 5 1 3 3 1 2 2 3 3 2 3 2 4 3 3 1 4 1 2 2 7 3 6 3 1 7 7 2 3 1 6 5	0 9 -1	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.

stud. Duţă Vlad

Râmnicu Vâlcea

vlad90vl@yahoo.com