문제
CPer인 소 M은 훈련 도중 실수로 문제를 잘못 읽어 아쉽게 0점을 받은 적이 있습니다. 시간이 흘러 지금 다시 돌아보니, 소 M은 그 잘못된 문제의 뜻 뒤에 흥미로운 이야기가 숨겨져 있었다는 것을 깨달았습니다... 어쩌면 이것이 당신에게 도전이 될지도 모릅니다.
과거로 돌아가 봅시다. 당신 앞에는 $n$명의 학생이 일렬로 서 있으며, 순서대로 $0, 1, 2, \dots, n-1$번으로 번호가 매겨져 있습니다. 당신은 이들에게 몇 곡의 노래를 가르치려 합니다. 노래는 총 $m$곡이 있으며, 순서대로 $0, 1, 2, \dots, m-1$번으로 번호가 매겨져 있습니다. 처음에 이 학생들은 아무 노래도 부를 줄 모릅니다.
당신은 이 학생들이 합창을 할 수 있게 되기를 바랍니다. $x$번 학생부터 시작하는 합창이란, $x$번 학생이 $0$번 노래를 부르고, $x+1$번 학생이 $1$번 노래를 부르며, $x+i$번 학생이 $i$번 노래를 부르는 것($\forall i \in [0, m)$)을 의미합니다. 만약 이 학생들이 각자 자신의 노래를 부를 수 있게 된다면, 이 합창 계획은 '달성 가능'하다고 합니다.
학생 번호는 순환하지 않으므로, 위 정의에서 유효하지 않은 번호가 나타나면 해당 합창 계획은 존재하지 않는 것으로 간주합니다.
당신은 분신술을 쓸 수 없으므로, 매 단위 시간마다 한 명에게 한 곡의 노래를 가르칠 계획입니다. 간단히 말해, 당신은 먼저 길이가 $S$인 커리큘럼 목록 $\Phi = \{(r_1, s_1), (r_2, s_2), \dots, (r_S, s_S)\}$를 정합니다. 여기서 $0 \le r \le n-1$, $0 \le s \le m-1$을 만족하며, 이 목록은 중복을 허용합니다. 매 단위 시간마다 당신은 커리큘럼 목록의 $S$가지 방법 중 하나를 독립적으로 균등 확률로 선택하여 $(r, s)$를 실행합니다. 즉, $r$번 학생에게 $s$번 노래를 가르칩니다. 기억력이 좋지 않아 동일한 커리큘럼을 반복해서 가르칠 수도 있습니다.
$1 \le p \le n$을 만족하는 모든 정수 $p$에 대하여, 달성 가능한 서로 다른 합창 계획이 적어도 $p$개 존재하게 되기까지 기대 몇 단위 시간이 걸리는지 구하십시오.
입력
첫 번째 줄에 세 정수 $n, m, S$ ($1 \le m \le n \le 80, 1 \le S \le 15000$)가 주어집니다.
다음 $S$줄에는 각각 두 정수 $r, s$ ($0 \le r \le n-1, 0 \le s \le m-1$)가 주어지며, 이는 커리큘럼 목록의 한 과정을 나타내고 $r$번 학생에게 $s$번 노래를 가르침을 의미합니다.
출력
한 줄에 $n$개의 정수를 출력하며, 이는 $p = 1, 2, \dots, n$일 때 각각에 대응하는 정답입니다. 만약 존재한다면 $998244353$으로 나눈 나머지를 출력하고, 그렇지 않으면 해당 위치에 $-1$을 출력하십시오.
형식적으로, $M = 998244353$이라 할 때, 정확한 답은 기약분수 $\frac{p}{q}$로 나타낼 수 있으며, 여기서 $p$와 $q$는 정수이고 $q \not\equiv 0 \pmod M$입니다. 출력해야 할 값은 $p \cdot q^{-1} \pmod M$이며, 이는 $0 \le x < M$이고 $qx \equiv p \pmod M$을 만족하는 유일한 정수 $x$입니다.
예제
예제 입력 1
2 1 2 0 0 1 0
예제 출력 1
1 3
예제 입력 2
5 2 4 0 0 1 1 2 0 3 1
예제 출력 2
665496239 332748126 -1 -1 -1
예제 입력 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
예제 출력 3
1 177465665 198136383 907170767 930038200 516623876 417879798 928849837 -1 -1
예제 입력 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
예제 출력 4
325476536 76195241 263824532 -1 -1