Se acerca el verano, y Carlos, un joven economista de Murcia, le propone a sus compañeros de oficina ir de vacaciones todos juntos a un lugar por decidir, plan que resuena con todos los presentes. Sin embargo, cuando llega la hora de decidir dicho lugar, ven que es imposible decidirse. Por lo tanto, deciden aplazar el viaje en grupo al año siguiente y, en su lugar, deciden que cada uno de ellos irá a un lugar distinto, para luego poder hablarlo y decidir cual es el mejor.

Además, piensan que sería buena idea que todos buscasen lugares que estuviesen a menos de una determinada distancia en coche, para que la comparación sea más objetiva. Como es imposible viajar en línea recta entre ciudades, atravesando otras, denominan como distancia a la suma de las longitudes de las carreteras que conectan las ciudades por las que hay que pasar en el recorrido. El problema ahora es que, al poner un límite a la distancia máxima que pueden recorrer, no son capaces de decidir a qué valor fijar dicho límite.

Dadas las longitudes de todas las carreteras, para cada una de las distancias propuestas por Carlos y sus compañeros, ¿podrías determinar el número de ciudades a las que se podría viajar, recorriendo, como máximo, dicha distancia?

Entrada

La primera línea contendrá tres enteros: ~n~ y ~m~ (~1 \le n, m \le 2 \cdot 10^{5}~), el número de ciudades y carreteras existentes, respectivamente, y ~q~ (~1 \le q \le 3 \cdot 10^{6}~), el número de distancias propuestas.

Las siguientes ~m~ líneas contendrán tres enteros: ~u_{i}~ y ~v_{i}~ (~1 \le u_{i}, v_{i} \le n~), las ciudades conectadas por la ~i~-ésima carretera, y ~d_{i}~ (~1 \le d_{i} \le 5 \cdot 10^{3}~), la longitud de la ~i~-ésima carretera (~1 \le i \le m~), respectivamente. Se garantiza que dos ciudades nunca van a estar conectadas por más de una carretera, y que una carretera nunca conectará una ciudad a ella misma.

La última línea contendrá ~q~ enteros: ~a_{j}~ (~1 \le a_{j} \le 10^{9}~), la ~j~-ésima distancia propuesta (~1 \le j \le q~).

Salida

Para cada distancia propuesta, se ha de imprimir un entero ~c~, el número de ciudades que se pueden visitar recorriendo, como máximo, dicha distancia. Se asume que se parte desde la primera ciudad (~i = 1~), y esta es siempre incluída en el recuento.

Puntuación

• 50 puntos: ~\max\left\{n,m\right\} \cdot q \le 3 \cdot 10^{6}~
• 50 puntos: Sin restricciones.

Ejemplo 1

Entrada

5 5 5
1 2 4
1 3 7
2 3 2
2 4 3
3 5 5
3 4 6 7 11

Salida

1 2 3 4 5

Ejemplo 2

Entrada

6 5 4
1 2 5
2 3 1
3 4 1
4 5 1
5 6 1
2 4 6 8

Salida

1 1 3 5