Sau một thời gian dài xa cách, Alice và Bob đã đoàn tụ. Họ sống tại một đất nước có $n$ thành phố, được đặt tên một cách sáng tạo từ thành phố 1 đến thành phố $n$. Bob đã lái xe từ nhà mình ở thành phố 1 đến nhà Alice ở thành phố $n$.

Khi Alice hỏi Bob về con đường anh đã đi, cô rất ngạc nhiên khi thấy anh không nhớ rõ. Bob là người làm việc hiệu quả, anh lái xe không nghỉ và biết rằng không có con đường nào nhanh hơn con đường anh đã đi. Anh cũng có một chiếc TraveLog mới tinh của Công ty Phiêu lưu Quốc gia (NAC)! Mỗi khi Bob lái xe qua một thành phố, TraveLog sẽ ghi lại khoảng thời gian từ lúc anh rời thành phố 1 cho đến khi anh đến thành phố hiện tại.

Trong sơ đồ trên, có hai con đường nhanh nhất có thể mà Bob có thể đi từ thành phố 1 đến thành phố $n$: $1 \to 2 \to 3 \to 5$ hoặc $1 \to 4 \to 5$. Cả hai con đường đều mất tổng cộng 9 đơn vị thời gian. Con đường đầu tiên sẽ có TraveLog là 0, 3, 7, 9, và con đường thứ hai sẽ có TraveLog là 0, 5, 9.

Thật không may, bộ nhớ trong TraveLog của Bob đã bị hỏng. Bob nghĩ rằng một số mốc thời gian đã mất, và các mốc thời gian còn lại bị xáo trộn một cách ngẫu nhiên. Với những gì còn sót lại trong TraveLog, bạn có thể khôi phục lại con đường của Bob không?

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa ba số nguyên $n$ ($2 \le n \le 2 \cdot 10^5$), $m$ ($1 \le m \le 3 \cdot 10^5$) và $d$ ($1 \le d \le n$), trong đó $n$ là số lượng thành phố trong đất nước, $m$ là số lượng đường một chiều giữa các thành phố, và $d$ là số lượng mốc thời gian còn lại trong TraveLog bị hỏng của Bob. Các thành phố được đánh số từ 1 đến $n$. Bob sống ở thành phố 1, và Alice sống ở thành phố $n$.

Mỗi dòng trong số $m$ dòng tiếp theo chứa ba số nguyên $u, v$ ($1 \le u, v \le n, u \neq v$) và $h$ ($1 \le h \le 10^6$). Mỗi dòng mô tả một con đường một chiều từ thành phố $u$ đến thành phố $v$ mất $h$ đơn vị thời gian để đi qua. Đảm bảo rằng luôn có ít nhất một con đường từ thành phố 1 đến thành phố $n$. Có thể có nhiều con đường giữa bất kỳ cặp thành phố nào.

Mỗi dòng trong số $d$ dòng tiếp theo chứa một số nguyên $t$ ($0 \le t \le 10^{18}$). Đây là những gì còn lại trong TraveLog của Bob. Mỗi dòng là một bản ghi về khoảng thời gian Bob đã lái xe từ thành phố 1 đến một thành phố khác trên con đường của mình. Các giá trị này được đảm bảo là phân biệt.

Dữ liệu ra

Định dạng đầu ra phụ thuộc vào số lượng con đường phù hợp với TraveLog của Bob.

• Nếu không có con đường nào phù hợp với TraveLog của Bob, in ra 0.
• Nếu có nhiều con đường phù hợp với TraveLog của Bob, in ra 1.
• Nếu không, trên dòng đầu tiên, in ra số lượng thành phố trên con đường của Bob. Trên các dòng tiếp theo, in ra các thành phố mà Bob đã đi qua, mỗi thành phố trên một dòng, theo thứ tự anh đã ghé thăm.

Ví dụ

Ví dụ 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

Ví dụ 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

Ví dụ 3

2 1 1
1 2 10
5

0