Après une longue séparation, Alice et Bob se sont retrouvés. Ils vivent dans un pays comptant $n$ villes, nommées de manière créative de la ville 1 à la ville $n$. Bob a conduit depuis son domicile dans la ville 1 jusqu'au domicile d'Alice dans la ville $n$.

Lorsque Alice a demandé à Bob quel chemin il avait emprunté, il a été stupéfait de constater qu'il ne s'en souvenait pas. Bob est efficace, il a conduit sans s'arrêter et sait qu'il n'existe aucun chemin plus rapide que celui qu'il a pris. Il possède également un tout nouveau journal de voyage (TraveLog) de la National Adventuring Company (NAC) ! Chaque fois que Bob traverse une ville, le TraveLog enregistre le temps écoulé entre son départ de la ville 1 et son arrivée dans la ville actuelle.

Dans la disposition ci-dessus, il existe deux chemins les plus rapides possibles que Bob peut emprunter de la ville 1 à la ville $n$ : $1 \to 2 \to 3 \to 5$ ou $1 \to 4 \to 5$. Les deux chemins prennent un total de 9 unités de temps. Le premier chemin aurait un TraveLog de 0, 3, 7, 9, et le second aurait un TraveLog de 0, 5, 9.

Malheureusement, la mémoire du TraveLog de Bob est corrompue. Bob pense que certains temps ont disparu et que les temps restants ont été mélangés arbitrairement. Étant donné ce qu'il reste du TraveLog, pouvez-vous reconstruire le chemin de Bob ?

Entrée

La première ligne de l'entrée contient trois entiers $n$ ($2 \le n \le 2 \cdot 10^5$), $m$ ($1 \le m \le 3 \cdot 10^5$) et $d$ ($1 \le d \le n$), où $n$ est le nombre de villes dans le pays, $m$ est le nombre de routes à sens unique entre ces villes, et $d$ est le nombre de temps restants dans le TraveLog corrompu de Bob. Les villes sont identifiées par un numéro, de 1 à $n$. Bob vit dans la ville 1 et Alice vit dans la ville $n$.

Chacune des $m$ lignes suivantes contient trois entiers $u$, $v$ ($1 \le u, v \le n, u \neq v$) et $h$ ($1 \le h \le 10^6$). Chaque ligne décrit une route à sens unique de la ville $u$ vers la ville $v$ qui prend $h$ unités de temps à parcourir. Il est garanti qu'il existe au moins un chemin de la ville 1 à la ville $n$. Il peut y avoir plusieurs routes entre deux villes données.

Chacune des $d$ lignes suivantes contient un entier unique $t$ ($0 \le t \le 10^{18}$). C'est ce qu'il reste du TraveLog de Bob. Chaque ligne est un enregistrement de la quantité de temps que Bob a mis pour conduire de la ville 1 à une autre ville sur son chemin. Ces valeurs sont garanties d'être distinctes.

Sortie

Le format de sortie dépend du nombre de chemins cohérents avec le TraveLog de Bob.

• S'il n'y a aucun chemin cohérent avec le TraveLog de Bob, affichez 0.
• Si plusieurs chemins sont cohérents avec le TraveLog de Bob, affichez 1.
• Sinon, sur la première ligne, affichez le nombre de villes sur le chemin de Bob. Sur les lignes suivantes, affichez les villes visitées par Bob, une par ligne, dans l'ordre de sa visite.

Exemples

Entrée 1

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

Sortie 1

3
1
4
5

Entrée 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

Sortie 2

1

Entrée 3

2 1 1
1 2 10
5

Sortie 3

0

Figure 1. Disposition des chemins les plus rapides de la ville 1 à la ville n.