Biblioteka
Jaś wybrał się do biblioteki. Po drodze zamyślił się i zbłądził. Gdy wreszcie otworzył drzwi które zdawały się prowadzić do jego osiedlowej biblioteki, znalazł się w bardzo dziwnym pomieszczeniu. Nie była to jego biblioteka. Dziwnym zrządzeniem losu trafił do Biblioteki. Książki rozmieszczone były w niej na wielu platformach. Niektóre platformy miały dołączone schody, którymi można było przejść na inną platformę (ale, co dziwne, nie można było nimi wrócić). Schody były w ciągłym ruchu – co chwilę zmieniały platformę, do której prowadziły.
Orangutan znajdujący się w bibliotece wskazał Jasiowi (nieco grubiańsko) platformę, na której znajduje się książka, po którą Jaś przyszedł. Biblioteka bardzo niepokoi Jasia, więc chce jak najszybciej zdobyć książkę.
Pomóż Jasiowi znaleźć najkrótszą trasę do książki, którą pragnie wypożyczyć.
Wejście
W pierwszej linii wejścia znajduje się liczba platform n oraz liczba schodów m. W kolejnych m liniach znajdują się opisy schodów:
p – platforma z której można wejść na schody,
k – długość schodów (liczba jednostek czasu potrzebnych na ich pokonanie),
w – liczba platform docelowych odwiedzanych przez schody,
p1, p1, ... pw – platformy, na które można zejść ze schodów, platforma docelowa zmienia się co jednostkę czasu, zaczynając od p1, w kolejności podanej na wejściu, po odwiedzeniu wszystkich wymienionych platform schody wracają do p1 i powtarzają cykl; zatem na platformę p1 można zejść w momentach 0, w, 2w itd., na platformę p2 można zejść w momentach 1, w+1, 2w+1, itd.
Następnie pojawi się
z – liczba zapytań,
oraz z linii z zapytaniami postaci:
s t – oznaczające zapytanie o najkrótszą trasę z platformy startowej s do platformy docelowej t.
Platformy są numerowane od zera. Liczba platform nie przekroczy 10000, liczba zapytań nie przekroczy 1000. Szukana trasa zawsze będzie istniała.

Wyjście
Dla każdego zapytania należy na wyjście wypisać liczbę jednostek czasu, jakie zajmie dotarcie z platformy s do platformy t, zaczynając podróż, w przypadku każdego zapytania, w momencie 0.
Przykład
Wejście
7 6
0 2 1 1
1 1 5 2 3 4 5 6
3 1 1 2
4 1 1 3
5 1 1 4
6 1 1 5
5
0 2
0 3
0 4
0 5
0 6

Wyjście
5
5
4
3
4