TraveLog

오랜 시간 헤어져 있던 Alice와 Bob이 다시 만났다. 두 사람은 $n$개의 도시가 있는 나라에 살고 있고, 도시는 참신하게도 도시 $1$부터 도시 $n$까지 이름이 붙어 있다. Bob은 도시 $1$에 있는 자기 집에서 도시 $n$에 있는 Alice의 집까지 차를 몰고 갔다.

Alice가 어떤 경로로 왔는지 묻자, Bob은 자신이 그 경로를 기억하지 못한다는 사실에 깜짝 놀랐다. Bob은 효율적이어서 도중에 멈추지 않고 운전했으며, 자기가 택한 경로보다 더 빠른 경로는 없다는 것을 알고 있다. 또한 Bob에게는 따끈따끈한 National Adventuring Company (NAC) TraveLog가 있다! Bob이 어떤 도시를 통과할 때마다 TraveLog는 그가 도시 $1$을 떠난 시각부터 현재 도시에 도착한 시각 사이의 시간을 기록한다.

위 그림에서는 Bob이 도시 $1$에서 도시 $n$까지 갈 수 있는 가장 빠른 경로가 두 가지 있다: $1 \to 2 \to 3 \to 5$ 또는 $1 \to 4 \to 5$. 두 경로 모두 총 $9$ 단위 시간이 걸린다. 첫 번째 경로의 TraveLog는 $0, 3, 7, 9$이고, 두 번째 경로의 TraveLog는 $0, 5, 9$이다.

안타깝게도 Bob의 TraveLog 메모리가 손상되었다. Bob은 일부 시간이 사라졌고, 남은 시간들은 임의로 뒤섞였다고 생각한다. TraveLog에 남은 기록이 주어졌을 때, 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의 TraveLog에 남아 있는 시간의 수이다. 도시는 $1$부터 $n$까지 번호로 구분한다. Bob은 도시 $1$에, Alice는 도시 $n$에 산다.

다음 $m$개의 줄에는 각각 세 정수 $u$, $v$ ($1 \le u,v \le n, u \ne v$), $h$ ($1 \le h \le 10^{6}$)가 주어진다. 각 줄은 도시 $u$에서 도시 $v$로 가는 데 $h$ 단위 시간이 걸리는 일방통행 도로를 나타낸다. 도시 $1$에서 도시 $n$으로 가는 경로가 적어도 하나 존재한다. 같은 두 도시 사이에 여러 도로가 있을 수 있다.

다음 $d$개의 줄에는 각각 정수 $t$ ($0 \le t \le 10^{18}$)가 주어진다. 이것이 Bob의 TraveLog에 남아 있는 기록이다. 각 줄은 Bob이 경로 상의 어떤 도시로 갈 때 도시 $1$에서 출발한 뒤 걸린 시간을 나타낸다. 이 값들은 모두 서로 다르다.

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

• Bob의 TraveLog와 일치하는 경로가 없으면 $0$을 출력한다.
• Bob의 TraveLog와 일치하는 경로가 여러 개면 $1$을 출력한다.
• 그렇지 않으면 첫 번째 줄에 Bob의 경로에 있는 도시의 수를 출력한다. 이후 줄에 Bob이 방문한 도시를 방문 순서대로 한 줄에 하나씩 출력한다.