長い別離の末、アリスとボブは再会しました。彼らは $n$ 個の都市がある国に住んでおり、都市には $1$ から $n$ までの名前が付けられています。ボブは自宅のある都市 $1$ からアリスの家がある都市 $n$ まで車で移動しました。

アリスがボブにどの経路を通ったのか尋ねたところ、ボブは自分が覚えていないことに驚きました。ボブは効率的で、一度も止まらずに運転しており、自分が通った経路よりも速い経路は存在しないことを知っています。また、彼は新しい「National Adventuring Company (NAC) TraveLog」を持っています！ボブが都市を通過するたびに、TraveLog は都市 $1$ を出発してから現在の都市に到着するまでの時間を記録します。

上の図において、ボブが都市 $1$ から都市 $n$ まで移動する最短経路は $1 \to 2 \to 3 \to 5$ と $1 \to 4 \to 5$ の2通りあります。どちらの経路も合計で $9$ 単位の時間を要します。最初の経路の TraveLog は $0, 3, 7, 9$ となり、2番目の経路の TraveLog は $0, 5, 9$ となります。

残念なことに、ボブの TraveLog のメモリが破損してしまいました。ボブはいくつかの時刻が消えてしまい、残りの時刻はランダムに入れ替わっていると考えています。残された TraveLog の情報から、ボブの経路を復元できますか？

入力

入力の最初の行には、3つの整数 $n$ ($2 \le n \le 2 \cdot 10^5$)、$m$ ($1 \le m \le 3 \cdot 10^5$)、$d$ ($1 \le d \le n$) が含まれます。ここで、$n$ は国内の都市数、$m$ は都市間の片道道路の数、$d$ はボブの破損した TraveLog に残っている時刻の数です。都市には $1$ から $n$ までの番号が付けられています。ボブは都市 $1$ に住んでおり、アリスは都市 $n$ に住んでいます。

続く $m$ 行の各行には、3つの整数 $u, v$ ($1 \le u, v \le n, u \neq v$) と $h$ ($1 \le h \le 10^6$) が含まれます。各行は、都市 $u$ から都市 $v$ への、移動に $h$ 単位の時間を要する片道道路を表します。都市 $1$ から都市 $n$ への経路は少なくとも1つ存在することが保証されています。任意の都市のペア間に複数の道路が存在する場合があります。

続く $d$ 行の各行には、単一の整数 $t$ ($0 \le t \le 10^{18}$) が含まれます。これがボブの TraveLog に残っている情報です。各行は、ボブが都市 $1$ から経路上の別の都市へ移動するのに要した時間の記録です。これらの値はすべて異なることが保証されています。

出力

出力形式は、ボブの TraveLog と矛盾しない経路の数によって異なります。

• ボブの TraveLog と矛盾しない経路が存在しない場合、0 を出力してください。
• 複数の経路がボブの TraveLog と矛盾しない場合、1 を出力してください。
• それ以外の場合、最初の行にボブの経路上の都市数を出力してください。続く行に、ボブが訪れた都市を訪れた順に1行ずつ出力してください。

入出力例

入力 1

5 5 2
1 2 3
2 3 4
3 5 2
1 4 5
4 5 4
5
9

出力 1

3
1
4
5

入力 2

6 8 2
1 2 1
2 3 2
3 6 8
1 4 3
4 5 4
5 6 4
5 2 7
1 6 13
0
3

出力 2

1

入力 3

2 1 1
1 2 10
5

出力 3

0

上の図において、ボブが都市 1 から都市 n まで移動する最短経路は 1 → 2 → 3 → 5 と 1 → 4 → 5 の2通りあります。