You are given a tree with n nodes (numbered from 1 to n) rooted at node 1. Also, each node has two values associated with it. The values for i-th node are ai and bi.

You can jump from a node to any node in its subtree. The cost of one jump from node x to node y is the product of ax and by. The total cost of a path formed by one or more jumps is sum of costs of individual jumps. For every node, calculate the minimum total cost to reach any leaf from that node. Pay attention, that root can never be leaf, even if it has degree 1.

Note that you cannot jump from a node to itself.

Input

The first line of input contains an integer n (2 ≤ n ≤ 105) — the number of nodes in the tree.

The second line contains n space-separated integers a1, a2, ..., an( - 105 ≤ ai ≤ 105).

The third line contains n space-separated integers b1, b2, ..., bn( - 105 ≤ bi ≤ 105).

Next n - 1 lines contains two space-separated integers ui and vi (1 ≤ ui, vi ≤ n) describing edge between nodes ui and vi in the tree.

Output

Output n space-separated integers, i-th of which denotes the minimum cost of a path from node i to reach any leaf.

Examples

Input

3
2 10 -1
7 -7 5
2 3
2 1


Output

10 50 0 

Input

4
5 -10 5 7
-8 -80 -3 -10
2 1
2 4
1 3


Output

-300 100 0 0 

Note

In the first example, node 3 is already a leaf, so the cost is 0. For node 2, jump to node 3 with cost a2 × b3 = 50. For node 1, jump directly to node 3 with cost a1 × b3 = 10.

In the second example, node 3 and node 4 are leaves, so the cost is 0. For node 2, jump to node 4 with cost a2 × b4 = 100. For node 1, jump to node 2 with cost a1 × b2 = - 400 followed by a jump from 2 to 4 with cost a2 × b4 = 100.
import java.io.*;
import java.util.*;

public class Main{
	static public class liChaoTreeMin {
		treeNode root;
		long minN,maxN;
		liChaoTreeMin(long min,long max){
			root=new treeNode(new long[] {0,inf});
			minN=min;
			maxN=max+1;
		}
		
		static class treeNode{
			long[]val;
			treeNode left,right;
			treeNode(long[]vals){
				val=new long[] {vals[0],vals[1]};
			}
		}
		static long inf=(long)1e18;
		static long valueAt(long[]line,long x) {
			return line[0]*x+line[1];
		}
		void add_line(long[]newLine) {
			add_line(newLine, root,minN,maxN);
		}
		treeNode add_line(long[]newLine,treeNode node,long left,long right) {
			if(node==null) {
				node=new treeNode(new long[] {0,inf});
			}
		    long mid=(left+right)/2;
			int cur=0,nw=1;
		    int dominatingAtLeft = valueAt(newLine, left) < valueAt(node.val, left) ? cur : nw;
		    int dominatingAtMid = valueAt(newLine, mid) < valueAt(node.val, mid) ? cur : nw;
		    
		    if(dominatingAtMid!=nw) {
		    	long[]tmp=newLine.clone();
		    	newLine=node.val.clone();
		    	node.val=tmp.clone();
		    }
		    
		    if(newLine[1]>=inf || right-left==1) {
		    	return node;
		    }
		    
		    if(dominatingAtLeft!=dominatingAtMid) {
		    	//intersection at left subtree
		    	node.left=add_line(newLine, node.left, left, mid);
		    	
		    }
		    else {
		    	//intersection at right subtree
		    	node.right=add_line(newLine, node.right, mid, right);
		    	
		    }
		    return node;
		}
		long get(long x) {
			return get(x, root, minN, maxN);
		}
		long get(long x, treeNode node, long left, long  right) {
			if(node==null) {
				return inf;
			}
		    long mid=(left + right)/2;
		    if(right-left==1) {
		        return valueAt(node.val, x);
		    }
		    if(x < mid) {
		        return Math.min(valueAt(node.val, x), get(x, node.left, left, mid));
		    }
		    return Math.min(valueAt(node.val, x), get(x, node.right, mid, right));
		    
		}
		
	}
	static LinkedList<Integer>[]adj;
	static liChaoTreeMin[]trees;
	static long[]a,b;
	static int n;
	static LinkedList<Integer>[]subtree;
	static long[]ans;
	static void dfs(int i,int par) {
		int biggestChild=-1;
		int size=0;
		for(int j:adj[i]) {
			if(j==par)continue;
			dfs(j, i);
			if(subtree[j].size()>size) {
				size=subtree[j].size();
				biggestChild=j;
			}
		}
		if(biggestChild==-1) {//leaf
			trees[i]=new liChaoTreeMin(-100000, 100000);
			subtree[i].add(i);
			trees[i].add_line(new long[] {b[i],0});
			return;
		}
		trees[i]=trees[biggestChild];
		subtree[i]=subtree[biggestChild];
		for(int j:adj[i]) {
			if(j==biggestChild)continue;
			while(!subtree[j].isEmpty()) {
				int node=subtree[j].poll();
				subtree[i].add(node);
				trees[i].add_line(new long[] {b[node],ans[node]});
			}
		}
		ans[i]=trees[i].get(a[i]);
		trees[i].add_line(new long[] {b[i],ans[i]});
		subtree[i].add(i);
	}
	static void main() throws Exception{
		n=sc.nextInt();
		adj=new LinkedList[n];
		subtree=new LinkedList[n];
		trees=new liChaoTreeMin[n];
		for(int i=0;i<n;i++) {
			adj[i]=new LinkedList<Integer>();
			subtree[i]=new LinkedList<Integer>();
		}
		a=sc.longArr(n);
		b=sc.longArr(n);
		for(int i=0;i<n-1;i++) {
			int x=sc.nextInt()-1,y=sc.nextInt()-1;
			adj[x].add(y);
			adj[y].add(x);
		}
		ans=new long[n];
		dfs(0, -1);
		for(int i=0;i<n;i++) {
			pw.print(ans[i]+" ");
		}
	}
	public static void main(String[] args) throws Exception{
		sc=new MScanner(System.in);
		pw = new PrintWriter(System.out);
		int tc=1;
//		tc=sc.nextInt();
		while(tc-->0)
			main();
		pw.flush();
	}
	static PrintWriter pw;
	static MScanner  sc;
	static class MScanner {
		StringTokenizer st;
		BufferedReader br;
		public MScanner(InputStream system) {
			br = new BufferedReader(new InputStreamReader(system));
		}
 
		public MScanner(String file) throws Exception {
			br = new BufferedReader(new FileReader(file));
		}
 
		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}
		public int[] intArr(int n) throws IOException {
	        int[]in=new int[n];for(int i=0;i<n;i++)in[i]=nextInt();
	        return in;
		}
		public long[] longArr(int n) throws IOException {
	        long[]in=new long[n];for(int i=0;i<n;i++)in[i]=nextLong();
	        return in;
		}
		public int[] intSortedArr(int n) throws IOException {
	        int[]in=new int[n];for(int i=0;i<n;i++)in[i]=nextInt();
	        shuffle(in);
	        Arrays.sort(in);
	        return in;
		}
		public long[] longSortedArr(int n) throws IOException {
	        long[]in=new long[n];for(int i=0;i<n;i++)in[i]=nextLong();
	        shuffle(in);
	        Arrays.sort(in);
	        return in;
		}
		public Integer[] IntegerArr(int n) throws IOException {
	        Integer[]in=new Integer[n];for(int i=0;i<n;i++)in[i]=nextInt();
	        return in;
		}
		public Long[] LongArr(int n) throws IOException {
	        Long[]in=new Long[n];for(int i=0;i<n;i++)in[i]=nextLong();
	        return in;
		}
		public String nextLine() throws IOException {
			return br.readLine();
		}
 
		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}
 
		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}
 
		public char nextChar() throws IOException {
			return next().charAt(0);
		}
 
		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}
 
		public boolean ready() throws IOException {
			return br.ready();
		}
 
		public void waitForInput() throws InterruptedException {
			Thread.sleep(3000);
		}
	}
	static void shuffle(int[]in) {
		for(int i=0;i<in.length;i++) {
			int idx=(int)(Math.random()*in.length);
			int tmp=in[i];
			in[i]=in[idx];
			in[idx]=tmp;
		}
	}
	static void shuffle(long[]in) {
		for(int i=0;i<in.length;i++) {
			int idx=(int)(Math.random()*in.length);
			long tmp=in[i];
			in[i]=in[idx];
			in[idx]=tmp;
		}
	}
}