Background

The Great Filter theory suggests that there are several critical stages in the development of a civilization, with extremely difficult-to-cross chasms between them, such that very few civilizations ever reach the stage of interstellar colonization. This theory is also considered an explanation for the Fermi paradox.

The Great Filter

Description

In this problem, we consider a civilization to have $n$ levels, which are further divided into $k$ stages. Specifically, we have an array $L_0, L_1, \dots, L_k$ satisfying $0 = L_0 < L_1 < \dots < L_k = n$, where civilization levels $L_{j-1} + 1$ through $L_j$ are considered to be in stage $j$.

We consider a directed graph $G = (V, E)$ that describes the means by which a civilization can reach its final level. If $(x, y) \in E$, it means a civilization at level $x$ can attempt to progress to level $y$ (note that $x < y$ is not guaranteed here!). Specifically, due to the existence of the Great Filter, if $x$ is a civilization in stage $j$, then $y$ can only be in stage $j$ or stage $j+1$. If $y$ also belongs to stage $j$, we consider this a "normal progression"; otherwise, if $y$ belongs to stage $j+1$, we consider this a "dangerous progression".

We assume human civilization is currently at level 1, and our goal is to reach level $i$. We need to plan a progression scheme. A scheme can be represented as a path from 1 to $n$. We define the difficulty of a scheme as follows: let a counter be initialized to $s = 0$. We consider this path in order: each time a "normal progression" occurs, $s \leftarrow s + 1$; each time a "dangerous progression" occurs, $s \leftarrow s \times 2$. The final value of $s$ is the difficulty of the progression scheme.

For each $1 \le i \le n$, please determine whether there exists a scheme to progress from level 1 to level $i$. If it exists, please plan a scheme such that the difficulty is minimized.

Input

The first line contains three positive integers $n, m, k$, representing the number of civilization levels, the number of edges in the graph, and the number of stages, respectively.

The next line contains $k-1$ positive integers, representing $L_1, \dots, L_{k-1}$, as described in the problem.

The next $m$ lines each contain two positive integers $x, y$, representing an edge.

Output

Output $n$ lines in total. The $i$-th line contains an integer representing the minimum difficulty to evolve from level 1 to level $i$. Since this number can be very large, you only need to output the result modulo $998244353$. If it is impossible to evolve to level $i$, output $-1$.

Examples

Input 1

6 6 2
3
1 2
2 3
3 4
4 5
5 6
2 6

Output 1

0
1
2
4
5
2

Input 2

(filter2.in)

Output 2

(filter2.ans)

Note

Pay attention to the modulo operation.

Input 3

(filter3.in)

Output 3

(filter3.ans)

Subtasks

Hint

The input file for this problem is within 10 MB, and the output file is within 5 MB. Please use efficient input and output methods.