J. Formación de Coro

Como CPer, mientras entrenaba, el pequeño M leyó por error un problema y, lamentablemente, obtuvo una puntuación de cero. Con el paso del tiempo, al mirar atrás, el pequeño M descubrió que detrás de ese enunciado erróneo se escondía una historia interesante... Quizás esto sea un desafío para ti.

Volvamos al pasado. Frente a ti hay $n$ estudiantes formados en una fila, numerados secuencialmente del $0, 1, 2, \dots, n-1$. Planeas enseñarles algunas canciones. Hay un total de $m$ canciones, numeradas del $0, 1, 2, \dots, m-1$. Al principio, ninguno de los estudiantes sabe cantar ninguna canción.

Deseas que estos estudiantes aprendan a realizar un coro. Se define un coro que comienza en el estudiante $x$ como aquel donde el estudiante $x$ canta la canción $0$, el estudiante $x+1$ canta la canción $1$, y el estudiante $x+i$ canta la canción $i$ ($\forall i \in [0, m)$). Si todos estos estudiantes aprenden sus respectivas canciones, entonces este plan de coro se considera alcanzable.

La numeración de los estudiantes no es cíclica, por lo que si en la definición anterior aparece una numeración no válida, se considera directamente que este plan de coro no existe.

Debido a que no puedes estar en varios lugares a la vez, planeas enseñar una canción a una persona por cada unidad de tiempo. En términos simples, primero determinas una lista de cursos de longitud $S$, $\Phi = \{(r_1, s_1), (r_2, s_2), \dots, (r_S, s_S)\}$, que satisface $0 \le r \le n-1$ y $0 \le s \le m-1$ para cada elemento, y esta lista puede contener elementos repetidos. En cada unidad de tiempo, elegirás de forma independiente y uniforme al azar un par $(r, s)$ de los $S$ planes de la lista de cursos, y ejecutarás ese curso, es decir, enseñarás a la persona $r$ a cantar la canción $s$. Como tienes mala memoria, también es posible que repitas la enseñanza del mismo curso.

Para todos los enteros positivos $p$ que satisfacen $1 \le p \le n$, calcula cuántas unidades de tiempo se esperan, en promedio, para que comiencen a existir al menos $p$ planes de coro diferentes que sean alcanzables.

Entrada

La primera línea contiene tres enteros $n, m, S$ ($1 \le m \le n \le 80, 1 \le S \le 15000$).

Las siguientes $S$ líneas contienen cada una dos enteros $r, s$ ($0 \le r \le n-1, 0 \le s \le m-1$), que representan un conjunto de cursos en la lista de cursos, indicando que se enseña al estudiante $r$ la canción $s$.

Salida

Una línea con $n$ enteros, que representan las respuestas correspondientes para $p = 1, 2, \dots, n$. Si existe, imprime el resultado módulo $998244353$; de lo contrario, imprime $-1$ directamente en la posición correspondiente.

Formalmente, sea $M = 998244353$. Se puede demostrar que la respuesta exacta se puede expresar como una fracción irreducible $\frac{p}{q}$, donde $p$ y $q$ son enteros y $q \not\equiv 0 \pmod M$. Debes imprimir $p \cdot q^{-1} \pmod M$, es decir, el entero $x$ que satisface $0 \le x < M$ y $qx \equiv p \pmod M$. Se puede demostrar que tal $x$ es único.

Ejemplos

Ejemplo 1

Entrada:

2 1 2
0 0
1 0

Salida:

1 3

Ejemplo 2

Entrada:

5 2 4
0 0
1 1
2 0
3 1

Salida:

665496239 332748126 -1 -1 -1

Ejemplo 3

Entrada:

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

Salida:

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

Ejemplo 4

Entrada:

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

Salida:

325476536 76195241 263824532 -1 -1