在分開許久之後，Alice 和 Bob 重逢了。他們住在一個擁有 $n$ 個城市的國家，這些城市被創意地命名為城市 1 到城市 $n$。Bob 從他位於城市 1 的家開車前往 Alice 位於城市 $n$ 的家。

當 Alice 問 Bob 他走了哪條路時，他驚訝地發現自己不記得了。Bob 很有效率，他開車時中途沒有停下來，並且知道沒有比他所走的路徑更快的路徑。他還有一台全新的國家冒險公司 (NAC) 旅行日誌 (TraveLog)！每當 Bob 開車經過一個城市時，旅行日誌都會記錄下他從城市 1 出發到抵達當前城市之間所花費的時間。

在下方的佈局中，Bob 從城市 1 到城市 $n$ 有兩條可能的「最快路徑」：$1 \to 2 \to 3 \to 5$ 或 $1 \to 4 \to 5$。兩條路徑總共都花費 9 個時間單位。第一條路徑的旅行日誌記錄為 0, 3, 7, 9，而第二條路徑的記錄為 0, 5, 9。

不幸的是，Bob 旅行日誌中的記憶損壞了。Bob 認為有些時間記錄遺失了，而剩下的時間記錄被隨意打亂了。給定旅行日誌中剩餘的記錄，你能重建 Bob 的路徑嗎？

輸入格式

輸入的第一行包含三個整數 $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$ 是 Bob 損壞的旅行日誌中剩餘的時間記錄數量。城市編號為 1 到 $n$。Bob 住在城市 1，Alice 住在城市 $n$。

接下來的 $m$ 行，每行包含三個整數 $u, v$ ($1 \le u, v \le n, u \neq v$) 和 $h$ ($1 \le h \le 10^6$)。每行描述一條從城市 $u$ 到城市 $v$ 的單向道路，通行需要 $h$ 個時間單位。保證至少存在一條從城市 1 到城市 $n$ 的路徑。任意兩個城市之間可能有多條道路。

接下來的 $d$ 行，每行包含一個整數 $t$ ($0 \le t \le 10^{18}$)。這是 Bob 旅行日誌中剩餘的記錄。每一行記錄了 Bob 從城市 1 開車到他路徑上另一個城市所花費的時間。保證這些數值各不相同。

輸出格式

輸出格式取決於與 Bob 的旅行日誌一致的路徑數量。

• 如果沒有與 Bob 的旅行日誌一致的路徑，輸出 0。
• 如果有多條路徑與 Bob 的旅行日誌一致，輸出 1。
• 否則，在第一行輸出 Bob 路徑上的城市數量。在接下來的行中，依序輸出 Bob 造訪過的城市，每行一個。

範例

範例輸入 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