Условие задачи
Теория Великого фильтра (The Great Filter) утверждает, что в процессе развития цивилизации существуют несколько важных этапов, между которыми лежат труднопреодолимые барьеры, из-за чего количество цивилизаций, способных достичь стадии межзвездной колонизации, крайне мало. Эта теория также считается одним из объяснений парадокса Ферми.
В этой задаче мы считаем, что существует $n$ уровней развития цивилизации, которые разделены на $k$ этапов. В частности, у нас есть массив $L_0, L_1, \dots, L_k$, удовлетворяющий условию $0 = L_0 < L_1 < \dots < L_k = n$, где уровни с $L_{j-1} + 1$ по $L_j$ считаются принадлежащими этапу $j$.
Ориентированный граф $G = (V, E)$ описывает способы, которыми цивилизация может достичь конечного уровня. Если $(x, y) \in E$, это означает, что цивилизация на уровне $x$ может попытаться перейти на уровень $y$ (заметим, что здесь не гарантируется $x < y$!). В частности, из-за существования Великого фильтра, если $x$ — это уровень этапа $j$, то $y$ может принадлежать только этапу $j$ или $j+1$. Если $y$ также принадлежит этапу $j$, мы называем это «обычным прогрессом», в противном случае, если $y$ принадлежит этапу $j+1$, мы называем это «опасным прогрессом».
Мы считаем, что человеческая цивилизация сейчас находится на уровне 1, и наша цель — достичь уровня $i$. Нам нужно спланировать путь развития. План можно представить как путь от 1 до $n$. Мы определяем сложность плана следующим образом: пусть счетчик изначально равен $s = 0$. Мы рассматриваем этот путь последовательно: каждый раз, когда происходит «обычный прогрессом», $s \leftarrow s + 1$, а каждый раз, когда происходит «опасный прогресс», $s \leftarrow s \times 2$. Итоговое значение $s$ является сложностью данного плана развития.
Для каждого $1 \le i \le n$ определите, существует ли план развития от уровня 1 до уровня $i$. Если он существует, найдите такой план, при котором сложность минимальна.
Входные данные
Первая строка содержит три целых положительных числа $n, m, k$, обозначающих количество уровней цивилизации, количество ребер в графе и количество этапов развития.
Следующая строка содержит $k-1$ целых положительных чисел, обозначающих $L_1, \dots, L_{k-1}$, как описано в условии.
Далее следуют $m$ строк, каждая из которых содержит два целых положительных числа $x, y$, обозначающих ребро.
Выходные данные
Выведите $n$ строк. В $i$-й строке выведите целое число — минимальную сложность развития от уровня 1 до уровня $i$. Поскольку это число может быть очень большим, выведите его значение по модулю $998244353$. Если достичь уровня $i$ невозможно, выведите $-1$.
Примеры
Входные данные 1
6 6 2 3 1 2 2 3 3 4 4 5 5 6 2 6
Выходные данные 1
0 1 2 4 5 2
Входные данные 2
(содержимое файла filter/filter2.in)
Выходные данные 2
(содержимое файла filter/filter2.ans)
Примечание
Обратите внимание на взятие по модулю.
Входные данные 3
(содержимое файла filter/filter3.in)
Выходные данные 3
(содержимое файла filter/filter3.ans)
Подзадачи
| Подзадача | Баллы | $n \le$ | $m \le$ | $k \le$ |
|---|---|---|---|---|
| 1 | 10 | $10^2$ | $200$ | $n$ |
| 2 | 15 | $10^5$ | $2 \times 10^5$ | $40$ |
| 3 | 10 | $3 \times 10^5$ | $5 \times 10^5$ | $n$ |
| 4 | 20 | $500$ | $10^3$ | $n$ |
| 5 | 20 | $3 \times 10^4$ | $6 \times 10^4$ | $n$ |
| 6 | 15 | $10^5$ | $2 \times 10^5$ | $n$ |
| 7 | 10 | $3 \times 10^5$ | $5 \times 10^5$ | $n$ |
Примечание
Входной файл задачи не превышает 10 МБ, выходной файл — 5 МБ. Пожалуйста, используйте быстрые методы ввода-вывода.