J. Układ chóralny

Jako CPer, mały M podczas treningu niefortunnie źle przeczytał zadanie i z żalem zdobył zero punktów. Czas płynie, a patrząc wstecz, mały M odkrywa, że za tym błędnym zrozumieniem zadania kryła się interesująca historia... Być może będzie to wyzwanie dla Ciebie.

Wróćmy do przeszłości. Przed Tobą stoi $n$ uczniów w rzędzie, ponumerowanych od $0, 1, 2, \dots, n-1$. Zamierzasz nauczyć ich kilku piosenek. Łącznie jest $m$ piosenek, ponumerowanych od $0, 1, 2, \dots, m-1$. Początkowo żaden z uczniów nie potrafi zaśpiewać żadnej piosenki.

Chcesz, aby uczniowie nauczyli się chórku. Definiujemy chór zaczynający się od ucznia $x$ jako sytuację, w której uczeń $x$ śpiewa piosenkę $0$, uczeń $x+1$ śpiewa piosenkę $1$, a uczeń $x+i$ śpiewa piosenkę $i$ ($\forall i \in [0, m)$). Jeśli wszyscy ci uczniowie potrafią zaśpiewać swoje piosenki, taki plan chóru nazywamy osiągalnym.

Numery uczniów nie są cykliczne, więc jeśli w powyższej definicji pojawi się nieprawidłowy numer ucznia, uznaje się, że taki plan chóru nie istnieje.

Ponieważ nie możesz być w kilku miejscach naraz, w każdej jednostce czasu zamierzasz nauczyć jedną osobę jednej piosenki. Mówiąc prościej, najpierw ustalasz listę kursów o długości $S$, $\Phi = \{(r_1, s_1), (r_2, s_2), \dots, (r_S, s_S)\}$, spełniającą warunki $0 \le r \le n-1$, $0 \le s \le m-1$, przy czym lista ta może zawierać powtórzenia. W każdej jednostce czasu losujesz niezależnie i jednostajnie z prawdopodobieństwem $1/S$ jedną z par $(r, s)$ z listy kursów i wykonujesz ten kurs, czyli uczysz osobę $r$ śpiewać piosenkę $s$. Ponieważ masz słabą pamięć, możesz wielokrotnie prowadzić ten sam kurs.

Dla wszystkich liczb całkowitych $p$ spełniających $1 \le p \le n$, oblicz, po ilu jednostkach czasu (wartość oczekiwana) zacznie istnieć co najmniej $p$ różnych osiągalnych planów chóru.

Wejście

Pierwsza linia zawiera trzy liczby całkowite $n, m, S$ ($1 \le m \le n \le 80, 1 \le S \le 15000$). Następnie $S$ linii, każda zawiera dwie liczby całkowite $r, s$ ($0 \le r \le n-1, 0 \le s \le m-1$), oznaczające kurs z listy, polegający na nauczeniu ucznia $r$ piosenki $s$.

Wyjście

Jedna linia zawierająca $n$ liczb całkowitych, reprezentujących odpowiedzi dla $p = 1, 2, \dots, n$. Jeśli rozwiązanie istnieje, wypisz wynik modulo $998244353$, w przeciwnym razie wypisz $-1$ na odpowiedniej pozycji.

Formalnie, niech $M = 998244353$. Można udowodnić, że dokładny wynik można przedstawić jako nieskracalny ułamek $\frac{p}{q}$, gdzie $p$ i $q$ są liczbami całkowitymi oraz $q \not\equiv 0 \pmod M$. Należy wypisać $p \cdot q^{-1} \pmod M$, czyli liczbę całkowitą $x$ spełniającą $0 \le x < M$ oraz $qx \equiv p \pmod M$. Można udowodnić, że takie $x$ jest wyznaczone jednoznacznie.

Przykład

Przykład 1

2 1 2
0 0
1 0

Wyjście 1

1 3

Przykład 2

5 2 4
0 0
1 1
2 0
3 1

Wyjście 2

665496239 332748126 -1 -1 -1

Przykład 3

10 1 13
0 0
1 0
2 0
3 0
3 0
3 0
3 0
4 0
5 0
6 0
6 0
6 0
7 0

Wyjście 3

1 177465665 198136383 907170767 930038200 516623876 417879798 928849837 -1 -1

Przykład 4

5 3 17
0 0
1 0
2 0
2 0
2 0
4 0
0 1
1 1
1 1
2 1
3 1
1 2
2 2
2 2
3 2
4 2
4 2

Wyjście 4

325476536 76195241 263824532 -1 -1