Будучи CPer-ом, во время тренировки Маленький М однажды по ошибке прочитал условие задачи неверно и, к сожалению, получил ноль баллов. Время шло, и теперь, оглядываясь назад, Маленький М обнаружил, что за этим ошибочным условием скрывалась интересная история... Возможно, это станет вызовом для тебя.

Вернемся в прошлое. Перед тобой $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$. Поскольку у тебя плохая память, ты можешь повторять одни и те же занятия.

Для всех целых чисел $p$, удовлетворяющих $1 \le p \le n$, найди ожидаемое количество единиц времени, по прошествии которых начнет существовать по крайней мере $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$, то есть такое целое число $x$, что $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