大フィルター (The Great Filter)

大フィルター理論 (The Great Filter) によると、文明の発展過程にはいくつかの重要な段階が存在し、各段階の間には極めて越えがたい溝が存在するため、最終的に星間植民が可能な段階に到達できる文明は極めて稀であるとされています。この理論はフェルミのパラドックスに対する一つの説明としても知られています。

本問題では、文明には $n$ 個のレベルが存在し、これら $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$ へ進歩する計画が存在するかを判定してください。存在する場合、困難度が最小となる計画を策定してください。

入力

1行目に3つの正整数 $n, m, k$ が与えられ、それぞれ文明のレベル数、グラフの辺数、文明のステージ数を表します。

続く1行に $k - 1$ 個の正整数が与えられ、問題文で定義された $L_1, \dots, L_{k-1}$ を表します。

続く $m$ 行の各行に、2つの正整数 $x, y$ が与えられ、辺 $(x, y)$ を表します。

出力

出力は合計 $n$ 行です。第 $i$ 行には、レベル $1$ からレベル $i$ へ進化するための最小困難度を整数で出力してください。この値は非常に大きくなる可能性があるため、$\text{mod } 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

(filter2.in を参照)

出力 2

(filter2.ans を参照)

注記

注意取模。

入力 3

(filter3.in を参照)

出力 3

(filter3.ans を参照)

小課題

100% のデータにおいて、$2 \le k \le n \le 3 \times 10^5, 1 \le m \le 5 \times 10^5, 1 \le x, y \le n$ を満たします。