En el país de IOI, donde vive JOI-kun, hay ~N~ pueblos, numerados del ~1~ al ~N~. Además, hay ~N-1~ carreteras en el país de IOI, numeradas del ~1~ al ~N-1~. La carretera ~j~ (~1 \leq j \leq N-1~) conecta los pueblos ~U_j~ y ~V_j~ en ambas direcciones. Es posible viajar de cualquier pueblo a cualquier otro utilizando varias carreteras. Ahora se celebrará una carrera de sellos en el país de IOI. Se instalará una estación de sellos en cada pueblo.

La estación de sellos en el pueblo ~i~ (~1 \leq i \leq N~) se instalará en el tiempo ~T_i~. JOI-kun decide participar en la carrera de sellos. En el tiempo ~0~, JOI-kun parte de uno de los pueblos. Además, JOI-kun tiene resistencia ~D~ en el tiempo ~0~.

Cuando JOI-kun se encuentra en la ciudad ~i~ en el tiempo ~t~, realiza las siguientes acciones:

1. Primero, si ya hay una estación de sellos instalada en la ciudad actual, presiona el sello. Es decir, presiona el sello si ~Ti \leq t~.
2. Luego, elige entre completar la ronda de sellos o trasladarse a otra ciudad. Sin embargo, solo puede elegir trasladarse a otra ciudad si existe una ciudad adyacente conectada a la ciudad ~i~ por un camino que aún no ha visitado, y su resistencia actual es de al menos ~1~.
3. Si JOI-kun elige trasladarse a otra ciudad, elige una ciudad ~j~ no visitada entre las ciudades conectadas a la ciudad ~i~ por un camino, y se traslada allí. Su resistencia disminuye en ~1~, y llega a la ciudad ~j~ en el tiempo ~t+1~.
4. Si JOI-kun decide completar la carrera de sellos, esta se considera exitosa si ha presionado un sello al menos una vez hasta ese momento, y puede recibir un regalo allí. De lo contrario, la carrera no se considera exitosa.

Suponga que todos los tiempos, excepto el tiempo de viaje entre ciudades, son despreciables. Tenga en cuenta que JOI-kun no puede permanecer en la misma ciudad.

Eres el organizador del evento. Si JOI-kun tiene éxito en la carrera de sellos, debes preparar regalos en las ciudades correspondientes. Sin embargo, la cantidad de regalos es limitada, por lo que deseas prepararlos en la menor cantidad de ciudades posible. Desafortunadamente, no sabes desde qué ciudad comenzará JOI-kun. Por lo tanto, para cada ~s~ (~1 \leq s \leq N~), debes encontrar la cantidad de ciudades en las que se deben preparar regalos cuando JOI-kun comience desde la ciudad ~s~. En otras palabras, debes contar el número de ciudades ~g~ (~1 \leq g \leq N~) tales que sea posible que la carrera de sellos sea exitosa cuando JOI-kun termine en la ciudad ~g~.

Conociendo las ciudades y carreteras del país de IOI, la resistencia de JOI-kun y los tiempos de instalación de las estaciones de sellos, escribe un programa que calcule, para cada ciudad, el número de ciudades en las que se deben preparar regalos cuando JOI-kun comience desde esa ciudad.

Entrada

La entrada es dada en el siguiente formato:

N D
T_1 T_2 ··· T_N
U_1 V_1
U_2 V_2
...
U_N-1 V_N-1

Salida

Escriba ~N~ líneas en la salida estándar. La ~s-~ésima línea (~1 \leq s \leq N~) debe contener el número de ciudades en las que se deben preparar regalos cuando JOI-kun parte de la ciudad ~s~.

Restricciones

• ~2 \leq N \leq 400 000~.
• ~0 \leq D \leq N-1~.
• ~0 \leq T_i \leq N~ (~1 \leq i \leq N~).
• ~1 \leq U_j < V_j \leq N~ (~1 \leq j \leq N-1~).
• Es posible viajar de cualquier ciudad a cualquier otra utilizando un número determinado de carreteras.
• Todos los valores dados son enteros.

Subtareas

Subtarea	Puntos	Restricciones adicionales
~1~	~3~	~D \leq 1~
~2~	~7~	~N \le 3000~, ~(U_j, V_j) = (j, j+1)~ (~1 \leq j \leq N-1~)
~3~	~10~	~N \leq 3000~
~4~	~11~	~(U_j, V_j) = (j, j+1)~ (~1 \leq j \leq N-1~)
~5~	~41~	~D = N-1~, ~N \leq 150\,000~
~6~	~28~	Sin restricciones adicionales

Ejemplos

Entrada 1

5 2
2 2 0 1 3
1 2
2 3
2 4
4 5

Salida 1

2
3
4
2
2

Mostramos un ejemplo de las acciones de JOI-kun cuando $s = 1$.

En el instante ~0~, JOI-kun se encuentra en la ciudad ~1~ y realiza las siguientes acciones:

• La estación de sellos en la ciudad ~1~ aún no se ha instalado, por lo que JOI-kun no presiona ningún sello.
• La resistencia actual de JOI-kun es ~2~. Se traslada a la ciudad ~2~, que es una de las ciudades no visitadas conectadas con la ciudad ~1~ por una carretera.
• La resistencia de JOI-kun disminuye en ~1~, y llega al pueblo ~2~ en el tiempo ~1~.

En el tiempo ~1~, JOI-kun se encuentra en el pueblo ~2~ y realiza las siguientes acciones:

• La estación de sellos en el pueblo ~2~ aún no está instalada, por lo que JOI-kun no presiona ningún sello.
• La resistencia actual de JOI-kun es ~1~. Se dirige al pueblo ~3~, uno de los pueblos no visitados conectados con el pueblo ~2~ por un camino.
• La resistencia de JOI-kun disminuye en ~1~, y llega al pueblo ~3~ en el tiempo ~2~.

En el tiempo ~2~, JOI-kun se encuentra en el pueblo ~3~ y realiza las siguientes acciones:

• La estación de sellos en el pueblo ~3~ ya está instalada, por lo que JOI-kun presiona un sello.
• JOI-kun decide terminar la carrera de sellos aquí. Como ya ha presionado un sello al menos una vez, la carrera de sellos es un éxito. Recibe un regalo allí.

Por lo tanto, cuando JOI-kun comienza en la ciudad ~1~ y termina la carrera de sellos en la ciudad ~3~, la carrera puede ser exitosa, por lo que es necesario preparar un regalo en la ciudad ~3~. Cuando JOI-kun comienza en la ciudad ~1~, los regalos deben prepararse únicamente en las ciudades ~3~ y ~4~, por lo que la primera línea de la salida debe ser ~2~. Asimismo, cuando JOI-kun comienza en la ciudad ~2~, los regalos deben prepararse únicamente en las ciudades ~3~, ~4~ y ~5~, por lo que la segunda línea de la salida debe ser ~3~.

Nota: Este ejemplo cumple con las restricciones de las subtareas ~3~ y ~6~.

Entrada 2

5 1
0 1 2 1 2
1 2
2 3
3 4
4 5

Salida 2

2
1
2
0
1

Nota: Este ejemplo cumple con las restricciones de las subtareas ~1, 2, 3, 4~ y ~6~.

Entrada 3

7 6
2 3 0 4 1 3 4
1 2
2 3
2 4
1 5
1 6
6 7

Salida 3

2
2
7
5
1
2
5

Nota: Este ejemplo satisface las restricciones de las subtareas ~3~, ~5~ y ~6~.