久别重逢后，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

Figure 1. Bob 从城市 1 到城市 n 的两条可能的“最快路径”示意图