As a CPer, when Little M was training, he once unfortunately misread a problem and regrettably ended up with a score of zero. Time passes, and looking back now, Little M discovers that behind this misread problem statement, there was actually a hidden, interesting story... Perhaps this will be a challenge for you. Back to the past. You have $n$ students standing in a row, labeled $0, 1, 2, \dots, n-1$. You intend to teach them some songs. There are $m$ songs in total, labeled $0, 1, 2, \dots, m-1$. Initially, none of the students know how to sing any of the songs. You want these students to be able to perform a chorus. A chorus starting from student $x$ is defined as student $x$ singing song $0$, student $x+1$ singing song $1$, and student $x+i$ singing song $i$ ($\forall i \in [0, m)$). If these students can all sing their assigned songs, this chorus plan is called achievable. Student labels are not circular, so if an illegal label appears in the definition above, the chorus plan is considered non-existent. Because you cannot be in two places at once, you intend to teach one student one song per unit of time. Simply put, you first determine a course list $\Phi = \{(r_1, s_1), (r_2, s_2), \dots, (r_S, s_S)\}$ of length $S$, satisfying $0 \le r \le n-1$ and $0 \le s \le m-1$ for each entry, and this list may contain duplicates. In each unit of time, you will choose one $(r, s)$ uniformly at random from the $S$ options in the course list and execute this course, which means teaching student $r$ to sing song $s$. Because your memory is not good, you might teach the same course repeatedly. For all positive integers $p$ such that $1 \le p \le n$, calculate the expected number of time units until there exist at least $p$ different chorus plans that are achievable.

Input

The first line contains three integers $n, m, S$ ($1 \le m \le n \le 80, 1 \le S \le 15000$). The next $S$ lines each contain two integers $r, s$ ($0 \le r \le n-1, 0 \le s \le m-1$), representing a course in the course list, meaning teaching student $r$ song $s$.

Output

Output $n$ integers in a single line, representing the answers for $p = 1, 2, \dots, n$ respectively. If a solution exists, output the result modulo $998244353$; otherwise, output $-1$ at the corresponding position. Formally, let $M = 998244353$. It can be proven that the exact answer can be expressed as an irreducible fraction $\frac{p}{q}$, where $p$ and $q$ are integers and $q \not\equiv 0 \pmod M$. You need to output $p \cdot q^{-1} \pmod M$, which is the integer $x$ satisfying $0 \le x < M$ and $qx \equiv p \pmod M$. It can be proven that such an $x$ is unique.

Examples

Input 1

2 1 2
0 0
1 0

Output 1

1 3

Input 2

5 2 4
0 0
1 1
2 0
3 1

Output 2

665496239 332748126 -1 -1 -1

Input 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

Output 3

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

Input 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

Output 4

325476536 76195241 263824532 -1 -1