Runda 4: Dorzecze

Limit czasowy: 2 sekundy
Limit pamięciowy: 32 MB

"Jeszcze tylko geografia" pomyślał Antek, otwierając nielubiany przez siebie zeszyt ćwiczeń. Chociaż zdążył się już przyzwyczaić do długich godzin spędzanych nad tym przedmiotem, tym razem miał więcej pracy niż zwykle. Chcąc nie chcąc, otworzył ćwiczenia na stronie z mapą hipsometryczną dorzecza Bokafango. Przyjrzał się jej dokładnie i przeczytał wszystkie polecenia. Jeszcze tylko łyk herbaty i... tego nie było w planach! Struga napoju zalała mapę, imitując meandry prawdziwej rzeki. Antek skrzywił się na samą myśl o tym, że trzeba będzie ją odtworzyć. Na szczęście do odrobienia zadania niezbędne są tylko wysokości n.p.m. miast leżących nad Bokafango lub jej dopływami. Antek zapamiętał, że wszystkie one leżały dokładnie na poziomicach. Oznaczenia poziomic nie zostały zalane, wie więc na jakich wysokościach mogły leżeć miasta. 

Dorzecze Bokafango jest dość specyficzne. Składa się z r rzek, z których każda - bezpośrednio lub pośrednio - wpada w końcu do rzeki głównej. Żadne dwa ujścia, czy to rzeki do rzeki czy też rzeki głównej do morza, nie pokrywają się. Nad każdym ujściem na pewno leży miasto przedstawione na mapie. Szczęśliwie dla Antka, znalazł on inną mapę dorzecza. Udało mu się zatem odtworzyć wysokości niektórych miast. Bokafango słynie ze swej bogatej wodnej fauny, nie powinno więc dziwić, że była to mapa z zaznaczonymi miastami, w których znajdują się stacje badawcze ichtiologów. Ponieważ badają oni w tym rejonie wpływ łączenia się rzek na różnorodność gatunkową ryb, między każdymi dwoma ujściami na pewno znalazło się zaznaczone miasto ze stacją.

Wysokości n.p.m. pozostałych miast Antek musi jednak uzupełnić sam. Zastanawia się teraz, na ile sposobów może to zrobić, wiedząc, że woda w rzekach nie ma w zwyczaju płynąć do góry. Niedawno Antek naczytał się o chińskim twierdzeniu o resztach, wystarczy mu więc odpowiedź podana modulo liczba pierwsza p.

Wejście

W pierwszym wierszu wejścia znajdują się trzy liczby naturalne: n, r, p, oznaczające odpowiednio liczbę miast na mapie, liczbę rzek oraz liczbę pierwszą z zadania (2<=n<=10⁵, 1<=r<=100, 2<=p<= 2000). Numery miast to liczby z zakresu od 1 do n. W kolejnych r wierszach znajdują się opisy rzek - po jednym w każdym wierszu. Opis rzeki składa się z jednej liczby k (k>=2), a następnie z k liczb, wszystkich różnych - kolejnych miast, przez które ta rzeka przepływa. Pierwsza podana jest rzeka główna. Każda rzeka wpada, bezpośrednio lub pośrednio, do rzeki głównej. Ujścia są jedynymi punktami wspólnymi dwóch rzek. Żadne ujście nie pokrywa się z żadnym źródłem rzeki ani z innym ujściem. W kolejnym wierszu znajduje się jedna liczba naturalna x (1<=x<=n). W każdym z następnych x wierszy jedna para liczb naturalnych a, b, oznaczająca, że wysokość n.p.m. miasta a jest równa b. W ostatnim wierszu jest jedna liczba naturalna h (1<=h<=10⁵). Następnie h liczb, uporządkowanych ściśle rosnąco - wysokości, na których mogą leżeć miasta. Wszystkie wysokości są nieujemnymi liczbami całkowitymi mniejszymi niż 10⁹.

Wyjście

Jedna liczba całkowita nieujemna - reszta z dzielenia przez p ilości poprawnych uzupełnień mapy.

Przykład

Dla danych wejściowych:

9 3 19
4 1 2 3 4
4 5 6 7 2
3 8 9 6
4
3 10
5 20
7 20
8 30
3 10 20 30

poprawną odpowiedzią jest:

10