J. Đội hình hợp xướng

Là một CPer, trong quá trình luyện tập, Tiểu M đã từng không may đọc nhầm một bài toán và đáng tiếc nhận điểm 0. Thời gian trôi qua, giờ đây nhìn lại, Tiểu M nhận ra đằng sau ý nghĩa sai lệch của bài toán đó lại ẩn chứa một câu chuyện thú vị... Có lẽ đây sẽ là thử thách dành cho bạn.

Quay lại quá khứ. Trước mặt bạn có $n$ học sinh đứng thành một hàng, được đánh số thứ tự từ $0, 1, 2, \dots, n-1$. Bạn dự định dạy họ một số bài hát. Có tất cả $m$ bài hát, được đánh số từ $0, 1, 2, \dots, m-1$. Ban đầu, các học sinh này không biết hát bài nào cả.

Bạn hy vọng các học sinh này có thể học được một đội hình hợp xướng. Định nghĩa một đội hình hợp xướng bắt đầu từ học sinh số $x$ là: học sinh số $x$ hát bài số $0$, học sinh số $x+1$ hát bài số $1$, học sinh số $x+i$ hát bài số $i$ ($\forall i \in [0, m)$). Nếu các học sinh này đều biết hát bài của mình, thì phương án hợp xướng này được gọi là có thể đạt được.

Số hiệu học sinh không tuần hoàn, vì vậy nếu trong định nghĩa trên xuất hiện số hiệu không hợp lệ, thì phương án hợp xướng đó được coi là không tồn tại.

Vì bạn không thể phân thân, mỗi đơn vị thời gian bạn dự định dạy một người một bài hát. Nói một cách đơn giản, bạn xác định trước một danh sách khóa học độ dài $S$ là $\Phi = \{(r_1, s_1), (r_2, s_2), \dots, (r_S, s_S)\}$, thỏa mãn $0 \le r \le n-1$, $0 \le s \le m-1$, và danh sách này có thể chứa các phần tử trùng lặp. Mỗi đơn vị thời gian, bạn sẽ chọn ngẫu nhiên một $(r, s)$ từ $S$ phương án trong danh sách khóa học với xác suất đồng nhất, sau đó thực hiện khóa học đó, tức là dạy học sinh số $r$ học bài hát số $s$. Vì trí nhớ không tốt, bạn cũng có thể dạy đi dạy lại cùng một khóa học.

Với mọi số nguyên dương $p$ thỏa mãn $1 \le p \le n$, hãy tính kỳ vọng sau bao nhiêu đơn vị thời gian thì bắt đầu tồn tại ít nhất $p$ phương án hợp xướng khác nhau mà các phương án này đều có thể đạt được.

Dữ liệu vào

Dòng đầu tiên gồm ba số nguyên $n, m, S$ ($1 \le m \le n \le 80, 1 \le S \le 15000$). $S$ dòng tiếp theo, mỗi dòng gồm hai số nguyên $r, s$ ($0 \le r \le n-1, 0 \le s \le m-1$), biểu thị một khóa học trong danh sách, nghĩa là dạy học sinh số $r$ bài hát số $s$.

Dữ liệu ra

Một dòng gồm $n$ số nguyên, biểu thị câu trả lời tương ứng cho $p = 1, 2, \dots, n$. Nếu tồn tại, hãy xuất kết quả lấy mô-đun $998244353$, nếu không, hãy xuất $-1$ tại vị trí tương ứng.

Một cách hình thức, gọi $M = 998244353$, có thể chứng minh rằng đáp án chính xác có thể biểu diễn dưới dạng phân số tối giản $\frac{p}{q}$, trong đó $p$ và $q$ là các số nguyên và $q \not\equiv 0 \pmod M$. Bạn cần xuất ra $p \cdot q^{-1} \pmod M$, tức là xuất số nguyên $x$ thỏa mãn $0 \le x < M$ và $qx \equiv p \pmod M$. Có thể chứng minh rằng $x$ thỏa mãn điều kiện là duy nhất.

Ví dụ

Ví dụ 1

2 1 2
0 0
1 0

Ví dụ 1

1 3

Ví dụ 2

5 2 4
0 0
1 1
2 0
3 1

Ví dụ 2

665496239 332748126 -1 -1 -1

Ví dụ 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

Ví dụ 3

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

Ví dụ 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

Ví dụ 4

325476536 76195241 263824532 -1 -1