오랜 시간 떨어져 지낸 앨리스와 밥이 재회했습니다. 그들은 $n$개의 도시가 있는 나라에 살고 있으며, 도시 이름은 창의적으로 1번부터 $n$번까지 붙여져 있습니다. 밥은 자신의 집이 있는 1번 도시에서 앨리스의 집이 있는 $n$번 도시까지 차를 몰고 갔습니다.

앨리스가 밥에게 어떤 경로로 왔는지 물었을 때, 밥은 자신이 기억하지 못한다는 사실에 당황했습니다. 밥은 효율적인 사람이라 쉬지 않고 운전했으며, 자신이 택한 경로보다 더 빠른 경로는 없다는 것을 알고 있습니다. 또한 그는 새로 산 국립 모험 회사(NAC)의 TraveLog를 가지고 있습니다! 밥이 도시를 지날 때마다, TraveLog는 1번 도시를 출발한 시점부터 현재 도시에 도착한 시점까지의 시간을 기록합니다.

위의 배치도에서 밥이 1번 도시에서 $n$번 도시까지 갈 수 있는 가장 빠른 경로는 $1 \to 2 \to 3 \to 5$ 또는 $1 \to 4 \to 5$ 두 가지가 있습니다. 두 경로 모두 총 9의 시간이 소요됩니다. 첫 번째 경로는 TraveLog에 0, 3, 7, 9가 기록되고, 두 번째 경로는 0, 5, 9가 기록됩니다.

불행히도 밥의 TraveLog 메모리가 손상되었습니다. 밥은 일부 시간이 사라졌고, 남은 시간들은 임의로 섞였다고 생각합니다. TraveLog에 남아 있는 정보를 바탕으로 밥의 경로를 복원할 수 있을까요?

입력

첫 번째 줄에는 세 정수 $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$개의 줄에는 각각 세 정수 $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}$)가 주어집니다. 이것이 밥의 TraveLog에 남아 있는 정보입니다. 각 줄은 밥이 1번 도시에서 경로상의 다른 도시로 이동하는 데 걸린 시간 기록입니다. 이 값들은 서로 다름이 보장됩니다.

출력

출력 형식은 밥의 TraveLog와 일치하는 경로의 수에 따라 달라집니다.

• 밥의 TraveLog와 일치하는 경로가 없으면 0을 출력합니다.
• 밥의 TraveLog와 일치하는 경로가 여러 개라면 1을 출력합니다.
• 그 외의 경우, 첫 번째 줄에 밥의 경로에 포함된 도시의 수를 출력합니다. 다음 줄부터는 밥이 방문한 도시를 방문한 순서대로 한 줄에 하나씩 출력합니다.

예제

예제 1

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

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

1

예제 3

2 1 1
1 2 10
5

0

Figure 1. 밥이 1번 도시에서 n번 도시까지 갈 수 있는 가장 빠른 경로 예시