Titi la serpiente coral descubrió un nido de ratas muy interesante, el nido está compuesto por habitaciones conectadas por túneles, en total existen \(N\) habitaciones y \(N-1\) túneles, un túnel conecta 2 habitaciones y puede ser atravesado por ambos sentidos, además se dió cuenta que siempre existe un camino entre cada par de habitaciones.

Titi se percató que algunas habitaciones contienen cierta cantidad de ratas. Titi se encuentra muy hambrienta y se pregunta para cada habitación cuántas ratas máximo podría comerse si es que entra al nido por dicha habitación. Como las habitaciones y los túneles son muy estrechos, Titi no puede regresar por los túneles que ya atravesó, además como Titi es muy caprichosa, si es que entra en alguna habitación que no contiene ratas, se sale inmediatamente del nido y deja de comer ratas.

Ayuda a Titi a averiguar para cada habitación cuál es el máximo número de ratas que puede comerse si es que entra al nido por dicha habitación.

La primera línea contiene un entero \(N\) (\(1 \le N \le 10^5\)): la cantidad de habitaciones que existen.

La siguiente línea contiene \(N\) números enteros \(r_i\) (\(0 \le r_i \le 10^4\)) separados por espacios, donde \(r_i\) es la cantidad de ratas que existen en la habitación \(i\).

Las siguientes \(N-1\) líneas contienen la descripción de los túneles. Cada línea contiene dos enteros \(a_i\), \(b_i\) (\(1 \le a_i, b_i \le N\), \(a_i \neq b_i\)), indicando que existe un túnel entre la habitación \(a_i\) y la habitación \(b_i\) (está garantizado que los túneles forman un árbol).

Imprime \(N\) líneas, en la \(i\)-ésima línea un número entero que indique el máximo número de ratas que Titi puede comerse si es que entra al nido por la habitación \(i\).