Tło problemu

Teoria Wielkiego Filtra (The Great Filter) sugeruje, że w procesie rozwoju cywilizacji istnieje kilka ważnych etapów, a między nimi znajdują się niezwykle trudne do pokonania bariery. W rezultacie bardzo niewiele cywilizacji osiąga etap kolonizacji międzygwiezdnej. Teoria ta jest również uważana za jedno z wyjaśnień paradoksu Fermiego.

Wielki Filtr

W tym zadaniu przyjmujemy, że istnieje $n$ poziomów cywilizacji, które są podzielone na $k$ etapów. Mamy tablicę $L_0, L_1, \dots, L_k$, spełniającą warunek $0 = L_0 < L_1 < \dots < L_k = n$, gdzie poziomy cywilizacji od $L_{j-1} + 1$ do $L_j$ uznaje się za znajdujące się w etapie $j$.

Przyjmujemy, że skierowany graf $G = (V, E)$ opisuje sposoby, w jakie cywilizacja może osiągnąć ostateczny poziom. Jeśli $(x, y) \in E$, oznacza to, że cywilizacja na poziomie $x$ może próbować awansować na poziom $y$ (uwaga: nie gwarantuje to, że $x < y$!). W szczególności, ze względu na istnienie "Wielkiego Filtra", jeśli $x$ jest cywilizacją na etapie $j$, to $y$ może znajdować się tylko na etapie $j$ lub $j+1$. Jeśli $y$ również należy do etapu $j$, uznajemy to za "zwykły postęp", w przeciwnym razie, jeśli $y$ należy do etapu $j+1$, uznajemy to za "niebezpieczny postęp".

Przyjmujemy, że cywilizacja ludzka znajduje się obecnie na poziomie 1, a naszym celem jest osiągnięcie poziomu $i$. Musimy zaplanować ścieżkę postępu. Plan można przedstawić jako ścieżkę od 1 do $n$. Definiujemy stopień trudności planu w następujący sposób: licznik $s$ jest początkowo równy $s = 0$. Rozważamy ścieżkę w kolejności: za każdym razem, gdy następuje "zwykły postęp", $s \leftarrow s + 1$, a za każdym razem, gdy następuje "niebezpieczny postęp", $s \leftarrow s \times 2$. Ostateczna wartość $s$ jest stopniem trudności danego planu postępu.

Dla każdego $1 \le i \le n$ sprawdź, czy istnieje plan postępu z poziomu 1 do poziomu $i$. Jeśli istnieje, zaplanuj ścieżkę tak, aby stopień trudności był minimalny.

Wejście

W pierwszej linii znajdują się trzy liczby całkowite $n, m, k$, oznaczające liczbę poziomów cywilizacji, liczbę krawędzi w grafie oraz liczbę etapów cywilizacji.

W kolejnej linii znajduje się $k-1$ liczb całkowitych, oznaczających $L_1, \dots, L_{k-1}$, zgodnie z treścią zadania.

W kolejnych $m$ liniach znajdują się po dwie liczby całkowite $x, y$, oznaczające krawędź.

Wyjście

Wypisz łącznie $n$ linii. W $i$-tej linii wypisz jedną liczbę całkowitą oznaczającą minimalny stopień trudności ewolucji z poziomu 1 do poziomu $i$. Ponieważ ta liczba może być bardzo duża, wypisz wynik modulo $998244353$. Jeśli ewolucja do poziomu $i$ jest niemożliwa, wypisz $-1$.

Przykład

Wejście 1

6 6 2
3
1 2
2 3
3 4
4 5
5 6
2 6

Wyjście 1

0
1
2
4
5
2

Podzadania

Dla 100% danych zachodzi $2 \le k \le n \le 3 \times 10^5$, $1 \le m \le 5 \times 10^5$, $1 \le x, y \le n$.

Wskazówki

Plik wejściowy ma rozmiar poniżej 10 MB, a plik wyjściowy poniżej 5 MB. Prosimy o korzystanie z szybkich metod wejścia i wyjścia.