J. Formation de chorale

En tant que CPer, lors d'un entraînement, le petit M a malheureusement mal lu un problème et a fini avec un score nul, ce qui est regrettable. Le temps passe, et en y repensant aujourd'hui, le petit M découvre qu'une histoire intéressante se cachait derrière l'énoncé erroné de ce problème... Peut-être que cela sera un défi pour vous.

Revenons en arrière. Devant vous, $n$ étudiants sont alignés, numérotés de $0, 1, 2, \dots, n-1$. Vous avez l'intention de leur apprendre quelques chansons. Il y a au total $m$ chansons, numérotées de $0, 1, 2, \dots, m-1$. Au début, aucun de ces étudiants ne sait chanter aucune chanson.

Vous souhaitez que ces étudiants apprennent à réaliser une chorale. On définit une chorale commençant à l'étudiant $x$ comme suit : l'étudiant $x$ chante la chanson $0$, l'étudiant $x+1$ chante la chanson $1$, et l'étudiant $x+i$ chante la chanson $i$ ($\forall i \in [0, m)$). Si ces étudiants savent tous chanter leur chanson respective, alors ce plan de chorale est dit réalisable.

Les numéros des étudiants ne sont pas cycliques ; par conséquent, si un numéro invalide apparaît dans la définition ci-dessus, on considère directement que ce plan de chorale n'existe pas.

Comme vous ne pouvez pas être partout à la fois, vous prévoyez d'enseigner une chanson à une personne par unité de temps. Plus précisément, vous déterminez d'abord une liste de cours de longueur $S$, $\Phi = \{(r_1, s_1), (r_2, s_2), \dots, (r_S, s_S)\}$, satisfaisant $0 \le r \le n-1$ et $0 \le s \le m-1$ pour chaque élément, et cette liste peut contenir des doublons. À chaque unité de temps, vous choisissez uniformément et aléatoirement un couple $(r, s)$ parmi les $S$ options de la liste de cours, puis vous exécutez ce cours, c'est-à-dire que vous apprenez à la personne $r$ à chanter la chanson $s$. Comme vous avez une mauvaise mémoire, il est possible que vous enseigniez plusieurs fois le même cours.

Pour tout entier positif $p$ tel que $1 \le p \le n$, calculez le nombre attendu d'unités de temps après lesquelles il existe au moins $p$ plans de chorale différents qui sont réalisables.

Entrée

La première ligne contient trois entiers $n, m, S$ ($1 \le m \le n \le 80, 1 \le S \le 15000$). Les $S$ lignes suivantes contiennent chacune deux entiers $r, s$ ($0 \le r \le n-1, 0 \le s \le m-1$), représentant un cours dans la liste de cours, signifiant l'apprentissage de la chanson $s$ par l'étudiant $r$.

Sortie

Une ligne contenant $n$ entiers, représentant les réponses correspondantes pour $p = 1, 2, \dots, n$. Si le résultat existe, affichez-le modulo $998244353$, sinon affichez $-1$ à la position correspondante.

Formellement, soit $M = 998244353$. On peut prouver que la réponse exacte peut être exprimée sous la forme d'une fraction irréductible $\frac{p}{q}$, où $p$ et $q$ sont des entiers et $q \not\equiv 0 \pmod M$. Vous devez afficher $p \cdot q^{-1} \pmod M$, c'est-à-dire l'entier $x$ tel que $0 \le x < M$ et $qx \equiv p \pmod M$. On peut prouver que cet entier $x$ est unique.

Exemples

Exemples 1

2 1 2
0 0
1 0

Sortie 1

1 3

Exemples 2

5 2 4
0 0
1 1
2 0
3 1

Sortie 2

665496239 332748126 -1 -1 -1

Exemples 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

Sortie 3

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

Exemples 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

Sortie 4

325476536 76195241 263824532 -1 -1