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

import java.io.*;
import java.util.*;
public class Main
{
    public static InputReader in = new InputReader(System.in);
    public static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args)
    {
        int n;
        n=in.nextInt();
        dsu_on_tree d=new dsu_on_tree(n+1);
        for(int i=1;i<=n;++i)
            d.ans2[i]=in.nextInt();
        for(int i=1;i<n;++i)
            d.insert(in.nextInt(),in.nextInt());
        d.topo(1);
        d.solve(n);
        for(int i=1;i<=n;++i)
            out.print(d.ans2[i]+" ");
        out.flush();
        out.close();
    }

}
class graph_list
{
    LinkedList<Integer> edge[];
    void add(int u,int v)
    {
        edge[u].add(v);
    }
    graph_list(int n)
    {
        edge=new LinkedList[n];
        for(int i=0;i<n;++i)
            edge[i]=new LinkedList<Integer>();
    }
}
class graph //前向星
{
    int Begin[], to[], Next[], e;
    void add(int u, int v)
    {
        to[++e] = v;
        Next[e] = Begin[u];
        Begin[u] = e;
    }
    graph(int a)
    {
        e=0;
        to=new int[a];
        Next=new int[a];
        Begin=new int[a];
        Arrays.fill(Begin,-1);
    }
}
class dsu_on_tree
{
    graph p;
    HashMap<Integer,Integer> ans[];
    int topo1[],time,fa[],K,sum[],max1[];
    long ans2[];
    dsu_on_tree(int n)
    {
        fa=new int[n+1];
        max1=new int[n+1];
        ans=new HashMap[n];
        ans2=new long[n+1];
        topo1=new int[n];
        p=new graph(2*n+10);
        for(int i=0;i<n;++i)
            ans[i]=new HashMap<Integer,Integer>();
    }
    void insert(int u,int v)
    {
        p.add(u,v);
        p.add(v,u);
    }
    void solve(int N)
    {
        for(int i=1;i<=N;++i)
        {
            ans[i].put((int)ans2[i],1);
            max1[i]=1;
        }
        for(int i=time-1;i>0;--i)
            ans[fa[topo1[i]]]=merge(ans[topo1[i]],ans[fa[topo1[i]]],topo1[i]);

    }
    HashMap<Integer,Integer> merge(HashMap<Integer,Integer> a,HashMap<Integer,Integer> b,int p)
    {
        if(a.size()>b.size())
        {
            ans2[fa[p]]=ans2[p];
            max1[fa[p]]=max1[p];
            p=fa[p];
            for(Map.Entry<Integer,Integer> i:b.entrySet())
            {
                if (a.containsKey(i.getKey())) {
                    int p2 = a.get(i.getKey());
                    if(max1[p]==p2+i.getValue())
                        ans2[p]+=(long)i.getKey();
                    else if(max1[p]<p2+i.getValue())
                    {
                        ans2[p]=(long)i.getKey();
                        max1[p]=p2+i.getValue();
                    }
                    a.replace(i.getKey(), p2 + i.getValue());
                }
                else
                    {
                    a.put(i.getKey(), i.getValue());
                        if (max1[p]==i.getValue())
                            ans2[p]+=(long)i.getKey();
                        else if(max1[p]<i.getValue())
                        {
                            ans2[p]=(long)i.getKey();
                            max1[p]=i.getValue();
                        }
                }
            }
            b.clear();
            return a;
        }
        p=fa[p];
        for(Map.Entry<Integer,Integer> i:a.entrySet()) {
            if (b.containsKey(i.getKey()))
            {
                int p2 = b.get(i.getKey());
                if(max1[p]==p2+i.getValue())
                    ans2[p]+=(long)i.getKey();
                else if(max1[p]<p2+i.getValue())
                {
                    ans2[p]=(long)i.getKey();
                    max1[p]=p2+i.getValue();
                }
                b.replace(i.getKey(), p2 + i.getValue());
            }
            else
                {
                b.put(i.getKey(), i.getValue());
                if (max1[p]==i.getValue())
                    ans2[p]+=(long)i.getKey();
                else if(max1[p]<i.getValue())
                {
                    ans2[p]=(long)i.getKey();
                    max1[p]=i.getValue();
                }
            }
        }
        a.clear();
        return b;
    }
    void topo(int root)
    {
        Arrays.fill(fa,-1);
        Arrays.fill(topo1,0);
        int que[]=new int[100010];
        int tail=0,head=0;
        int cur=0;
        que[tail++]=root;
        time=0;
        while (tail!=head)
        {
            cur=que[head++];
            topo1[time++]=cur;
            for(int i=p.Begin[cur];i!=-1;i=p.Next[i])
                if(p.to[i]!=fa[cur])
                {
                    que[tail++]=(p.to[i]);
                    fa[p.to[i]]=cur;
                }
        }
    }
}
class tree_split
{
    graph p;
    int dep[],fa[],top[],size1[],son[],id[],weight[],new_weight[];
    int len;
    void query(tree_array1 p,int x,int y,int k) //区间加值 query具体看题目写 输入原树编号
    {
        while(top[x]!=top[y])
        {
            if(dep[top[x]]<dep[top[y]]){ int mid=x;x=y;y=mid;}
            p.range_add(id[top[x]],id[x],k);
            x=fa[top[x]];
        }
        if(dep[x]>dep[y]){ int mid=x;x=y;y=mid;}
        p.range_add(id[x],id[y],k);
    }
    long query2(tree_array1 p,int x,int y) //区间询问 query具体看题目写 输入原树编号
    {
        long ans=0;
        while(top[x]!=top[y])
        {
            if(dep[top[x]]<dep[top[y]]){ int mid=x;x=y;y=mid;}
            ans+=p.range_ask(id[top[x]],id[x]);
            x=fa[top[x]];
        }
        if(dep[x]>dep[y]){ int mid=x;x=y;y=mid;}
        ans+=p.range_ask(id[x],id[y]);
        return ans;
    }

    tree_split(int n,int m)
    {
        dep=new int[n+3];
        fa=new int[n+3];
        top=new int[n+3];
        size1=new int[n+3];
        son=new int[n+3];
        id=new int[n+3];
        weight=new int[n+3];
        new_weight=new int[n+3];
        Arrays.fill(fa,0);
        Arrays.fill(top,0);
        Arrays.fill(size1,0);
        Arrays.fill(son,0);
        p=new graph(m);
        len=0;
    }
    void init(int root)
    {
        dep[root]=0;
        dfs1(root,root);
        dfs2(root,root);
    }
    void add_weight(int i,int w)
    {
        weight[i]=w;
    }
    void add_edge(int u,int v)
    {
        p.add(u,v);
    }
    void dfs0(int u) //单纯用来求LCA的dfs
    {
        int maxx=0,son=0;
        top[u]=u;
        size1[u]=1;
        for(int i=p.Begin[u];i!=-1;i=p.Next[i])
        {
            if(p.to[i]==fa[u])
                continue;
            fa[p.to[i]]=u;
            dep[p.to[i]]=dep[u]+1;
            dfs0(p.to[i]);
            size1[u]+=size1[p.to[i]];
            if(size1[p.to[i]]>maxx)
            {
                son=p.to[i];
                maxx = size1[son];
            }
        }
        if(son!=0)
            top[son]=u;
    }
    void dfs1(int u,int father)//一和二是完整树链剖分的预处理
    {
        dep[u]=dep[father]+1;
        fa[u]=father;
        size1[u]=1;
        for(int i=p.Begin[u];i!=-1;i=p.Next[i])
        {
            if(p.to[i]!=father)
            {
                dfs1(p.to[i],u);
                size1[u]+=size1[p.to[i]];
                if(size1[p.to[i]]>size1[son[u]])
                    son[u]=p.to[i];
            }
        }
    }
    void dfs2(int u,int topf)
    {
        id[u]=++len;
        new_weight[len]=weight[u];
        top[u]=topf;
        if(son[u]==0)return;
        dfs2(son[u],topf);
        for(int i=p.Begin[u];i!=-1;i=p.Next[i])
        {
            if(p.to[i]==fa[u] || p.to[i]==son[u]) continue;
            dfs2(p.to[i],p.to[i]);
        }
    }
    int find(int u)
    {
        return top[u] = top[u] == u ? u : find(top[u]);
    }
    int LCA(int u, int v) {
        if (find(u) != find(v))
            return dep[top[u]] > dep[top[v]] ? LCA(fa[top[u]], v) : LCA(u, fa[top[v]]);
        else return dep[u] > dep[v] ? v : u;
    }
}
class tree_array1  //区间修改 + 区间和
{
    long sum1[],sum2[];
    long a[]; //原序列
    int n;
    tree_array1(int n1)
    {
        n=n1;
        sum1=new long[n+1];
        a=new long[n+1];
        sum2=new long[n+1];
    }
    void init()
    {
        for(int i=1;i<=n;++i)
            a[i]+=a[i-1];
        Arrays.fill(sum1,0);
        Arrays.fill(sum2,0);
    }
    void add(int p, long x){
        for(int i = p; i <= n; i += i & -i)
        {
            sum1[i] += x;
            sum2[i] += x * p;
        }
    }
    void range_add(int l, int r, long x){
        add(l, x);
        add(r + 1, -x);
    }
    long ask(int p){
        long res = 0;
        for(int i = p; i!=0; i -= i & -i)
            res += (p + 1) * sum1[i] - sum2[i];
        return res;
    }
    long range_ask(int l, int r){
        return ask(r) - ask(l - 1)+a[r]-a[l-1];
    }
}
class InputReader{
    private final static int BUF_SZ = 65536;
    BufferedReader in;
    StringTokenizer tokenizer;
    public InputReader(InputStream in) {
        super();
        this.in = new BufferedReader(new InputStreamReader(in),BUF_SZ);
        tokenizer = new StringTokenizer("");
    }
    public String next() {
        while (!tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(in.readLine());
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }
    public boolean hasNext() {  //处理EOF
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                String line = in.readLine();
                if(line == null) return false;
                tokenizer = new StringTokenizer(line);
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return true;
    }
    public int nextInt() {
        return Integer.parseInt(next());
    }
    public long nextLong()
    {
        return Long.parseLong(next());
    }
}