小维佳喜欢在河上航行。但如果乘船航行超过 $k$ 小时，他就会晕船，因此他不会乘坐这样的船。河上有 $n$ 个港口，按照河流的方向（从上游到下游）依次编号为 $1$ 到 $n$。船在任意两个相邻港口之间航行恰好需要一小时。维佳知道河上的所有航线。每条航线连接两个不同的港口。他只保留了航行时间不超过 $k$ 小时的航线，最终得到了一个仅包含 $m$ 条航线的列表。

现在维佳想要旅行。他制定了一个旅行计划，这是一个由若干个（不一定不同）港口组成的有序列表，表示他希望依次访问这些港口。但事实证明这次旅行不够经济，因此维佳决定从他的列表中删除一些港口。他希望按如下规则进行删除：第一个港口保留在列表中；对于后续的每个港口，当且仅当它与前一个未被删除的港口不同，且可以从前一个未被删除的港口出发（可能需要换乘）始终沿着同一个方向（要么总是顺流，要么总是逆流）到达时，该港口才会被保留在列表中。

帮助维佳得到他最终的旅行路线。

输入格式

第一行包含三个整数 $n$、$m$ 和 $k$（$2 \le n \le 2 \cdot 10^5$，$0 \le m \le 2 \cdot 10^5$，$1 \le k \le 200$）。

接下来的 $m$ 行描述了这些航线。其中的每一行包含两个整数 $u_i$ 和 $v_i$（$1 \le u_i < v_i \le n$，$v_i - u_i \le k$），表示由该航线连接的两个港口的编号。

下一行包含一个整数 $q$（$1 \le q \le 2 \cdot 10^5$），表示计划中的港口数量。

最后一行包含 $q$ 个整数 $x_1, \dots, x_q$（$1 \le x_i \le n$，$x_i \ne x_{i+1}$），表示计划中依次访问的港口编号。

输出格式

以与输入相同的格式输出最终的旅行计划：第一行输出旅行计划中的港口总数，第二行按访问顺序输出这些港口的编号。

样例

输入样例 1

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

输出样例 1

3
4 1 2