You are given a rooted tree with root in vertex 1. Each vertex is coloured in some colour.

Let's call colour c dominating in the subtree of vertex v if there are no other colours that appear in the subtree of vertex v more times than colour c. So it's possible that two or more colours will be dominating in the subtree of some vertex.

The subtree of vertex v is the vertex v and all other vertices that contains vertex v in each path to the root.

For each vertex v find the sum of all dominating colours in the subtree of vertex v.

Input

The first line contains integer n (1 ≤ n ≤ 105) — the number of vertices in the tree.

The second line contains n integers ci (1 ≤ ci ≤ n), ci — the colour of the i-th vertex.

Each of the next n - 1 lines contains two integers xj, yj (1 ≤ xj, yj ≤ n) — the edge of the tree. The first vertex is the root of the tree.

Output

Print n integers — the sums of dominating colours for each vertex.

Examples

Input

4
1 2 3 4
1 2
2 3
2 4


Output

10 9 3 4


Input

15
1 2 3 1 2 3 3 1 1 3 2 2 1 2 3
1 2
1 3
1 4
1 14
1 15
2 5
2 6
2 7
3 8
3 9
3 10
4 11
4 12
4 13


Output

6 5 4 3 2 3 3 1 1 3 2 2 1 2 3
/*
If you want to aim high, aim high
Don't let that studying and grades consume you
Just live life young
******************************
What do you think? What do you think?
1st on Billboard, what do you think of it
Next is a Grammy, what do you think of it
However you think, I’m sorry, but shit, I have no fcking interest
*******************************
I'm standing on top of my Monopoly board
That means I'm on top of my game and it don't stop
til my hip don't hop anymore
https://www.a2oj.com/Ladder16.html
*******************************
300iq as writer = Sad!
*/
import java.util.*;
import java.io.*;
import java.math.*;

   public class x600E
   {
      static int[] arr;
      static ArrayDeque<Integer>[] edges;
      public static void main(String hi[]) throws Exception
      {
         BufferedReader infile = new BufferedReader(new InputStreamReader(System.in));
         StringTokenizer st = new StringTokenizer(infile.readLine());
         int N = Integer.parseInt(st.nextToken());
         arr = new int[N+1];
         st = new StringTokenizer(infile.readLine());
         for(int i=0; i < N; i++)
            arr[i+1] = Integer.parseInt(st.nextToken());
         maps = new HashMap[N+1];
         for(int i=1; i <= N; i++)
            maps[i] = new HashMap<Integer, Integer>();
         edges = new ArrayDeque[N+1];
         for(int i=1; i <= N; i++)
            edges[i] = new ArrayDeque<Integer>();
         for(int i=0; i < N-1; i++)
         {
            st = new StringTokenizer(infile.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            edges[a].add(b);  edges[b].add(a);
         }
         val = new long[N+1];
         freq = new int[N+1];
         for(int v=1; v <= N; v++)
         {
            push(maps[v], arr[v], 1);
            val[v] = arr[v];
            freq[v] = 1;
         }
         dfs(1, 0);
         StringBuilder sb = new StringBuilder();
         for(int i=1; i <= N; i++)
            sb.append(val[i]+" ");
         System.out.println(sb);
      }
      static HashMap<Integer, Integer>[] maps;
      static long[] val;
      static int[] freq;
      public static void dfs(int curr, int par)
      {
         for(int next: edges[curr])
            if(next != par)
            {
               dfs(next, curr);
               HashMap<Integer, Integer> child = maps[next];
               if(child.size() <= maps[curr].size())
               {
                  for(int v: child.keySet())
                  {
                     push(maps[curr], v, child.get(v));
                     if(maps[curr].get(v) > freq[curr])
                     {
                        val[curr] = v;
                        freq[curr] = maps[curr].get(v);
                     }
                     else if(maps[curr].get(v) == freq[curr])
                        val[curr] += v;
                  }
               }
               else
               {
                  for(int v: maps[curr].keySet())
                  {
                     boolean lol = push(child, v, maps[curr].get(v));
                     if(child.get(v) > freq[curr])
                     {
                        val[curr] = v;
                        freq[curr] = child.get(v);
                     }
                     else if(child.get(v) == freq[curr] && !lol)
                        val[curr] += v;
                  }
                  if(freq[next] > freq[curr])
                  {
                     val[curr] = val[next];
                     freq[curr] = freq[next];
                  }
                  else if(freq[next] == freq[curr])
                     val[curr] += val[next];
                  maps[curr] = child;
               }
            }
      } 
      public static boolean push(HashMap<Integer, Integer> map, int k, int v)
      {
         boolean lol = false;
         if(!map.containsKey(k))
         {
            map.put(k, 0);
            lol = true;
         }
         map.put(k, map.get(k)+v);
         return lol;
      }
   }