In the intergalactic empire Bubbledom there are N planets, of which some pairs are directly connected by two-way wormholes. There are N-1 wormholes. The wormholes are of extreme religious importance in Bubbledom, a set of planets in Bubbledom consider themselves one intergalactic kingdom if and only if any two planets in the set can reach each other by traversing the wormholes. You are given that Bubbledom is one kingdom. In other words, the network of planets and wormholes is a tree.

However, Bubbledom is facing a powerful enemy also possessing teleportation technology. The enemy attacks every night, and the government of Bubbledom retakes all the planets during the day. In a single attack, the enemy attacks every planet of Bubbledom at once, but some planets are more resilient than others. Planets are number 0,1,…,N-1 and the planet i will fall with probability p_i. Before every night (including the very first one), the government reinforces or weakens the defenses of a single planet.

The government of Bubbledom is interested in the following question: what is the expected number of intergalactic kingdoms Bubbledom will be split into, after a single enemy attack (before they get a chance to rebuild)? In other words, you need to print the expected number of connected components after every attack.

Input

The first line contains one integer number N (1 ≤ N ≤ 10^5) denoting the number of planets in Bubbledom (numbered from 0 to N-1). 

The next line contains N different real numbers in the interval [0,1], specified with 2 digits after the decimal point, denoting the probabilities that the corresponding planet will fall.

The next N-1 lines contain all the wormholes in Bubbledom, where a wormhole is specified by the two planets it connects.

The next line contains a positive integer Q (1 ≤ Q ≤ 10^5), denoting the number of enemy attacks.

The next Q lines each contain a non-negative integer and a real number from interval [0,1], denoting the planet the government of Bubbledom decided to reinforce or weaken, along with the new probability that the planet will fall.

Output

Output contains Q numbers, each of which represents the expected number of kingdoms that are left after each enemy attack. Your answers will be considered correct if their absolute or relative error does not exceed 10^{-4}. 

Example

Input

5
0.50 0.29 0.49 0.95 0.83
2 3
0 3
3 4
2 1
3
4 0.66
1 0.69
0 0.36


Output

1.68040
1.48440
1.61740
import java.io.*;
import java.util.*;
import java.util.concurrent.TimeUnit;

public class d1045 implements Runnable{
	
    public static void main(String[] args) {
    	try{
            new Thread(null, new d1045(), "process", 1<<26).start();
        }
        catch(Exception e){
            System.out.println(e);
        }
    }
	public void run() {
		FastReader scan = new FastReader();
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
		//PrintWriter out = new PrintWriter("file.out");
		Task solver = new Task();
		//int t = scan.nextInt();
		int t = 1;
		for(int i = 1; i <= t; i++) solver.solve(i, scan, out);
		out.close();
	}

	static class Task {
		static final int oo = Integer.MAX_VALUE;
		static final long OO = Long.MAX_VALUE;

		static double[] probs;
		static List<List<Integer>> adj = new ArrayList<>();
		static double pairs = 0;
		public void solve(int testNumber, FastReader sc, PrintWriter out) {
			int N = sc.nextInt();
			probs = new double[N];
			double sum = 0;
			for(int i = 0; i < N; i++) {
				probs[i] = 1 - sc.nextDouble();
				sum += probs[i];
				adj.add(new ArrayList<>());
			}
			//System.out.println(sum);
			
			for(int i = 0; i < N-1; i++) {
				int u = sc.nextInt();
				int v = sc.nextInt();
				adj.get(u).add(v);
				adj.get(v).add(u);
			}
			children = new double[N];
			parent = new int[N];
			dfs(0, -1);
			//System.out.println(pairs);
			
			int Q = sc.nextInt();
			while(Q --> 0) {
				int u = sc.nextInt();
				double prob = sc.nextDouble();
				
				sum = sum - probs[u] + ( 1 - prob);
				
				if(parent[u] != -1)
					pairs -= probs[parent[u]] * children[parent[u]];
				pairs -= probs[u] * children[u];
				if(parent[u] != -1)
					children[parent[u]] = children[parent[u]] - probs[u] + 1 - prob;
				probs[u] = 1 - prob;
				
				if(parent[u] != -1)
					pairs += probs[parent[u]] * children[parent[u]];
				pairs += probs[u] * children[u];
				out.println(sum - pairs);
			}
		}
		
		static void dfs(int node, int par) {
			parent[node] = par;
			double sum = 0;
			for(int each: adj.get(node)) {
				if(each != par) {
					pairs += probs[each] * probs[node];
					sum += probs[each];
					dfs(each, node);
				}
			}
			children[node] = sum;
		}
		
		static double[] children;
		static int[] parent;
	}
	
	static long modDivide(long a, long b, long MOD) {
		a %= MOD;
		return (binpow(b, MOD-2, MOD) * a) % MOD;
	}
	static long binpow(long a, long b, long m) {
		a %= m;
		long res = 1;
		while (b > 0) {
			if ((b & 1) == 1)
				res = res * a % m;
			a = a * a % m;
			b >>= 1;
		}
		return res;
	}
	static int[] reverse(int a[]) 
    { 
        int[] b = new int[a.length]; 
        for (int i = 0, j = a.length; i < a.length; i++, j--) { 
            b[j - 1] = a[i]; 
        } 
        
        return b;
    }
	static long[] reverse(long a[]) 
    { 
        long[] b = new long[a.length]; 
        for (int i = 0, j = a.length; i < a.length; i++, j--) { 
            b[j - 1] = a[i]; 
        } 
        
        return b;
    }
	static void sort(int[] x){
		shuffle(x);
		Arrays.sort(x);
	}
	static void sort(long[] x){
		shuffle(x);
		Arrays.sort(x);
	}
	static class tup implements Comparable<tup>, Comparator<tup>{
		int a, b;
		tup(int a,int b){
			this.a=a;
			this.b=b;
		}
		public tup() {
		}
		@Override
		public int compareTo(tup o){
			return Integer.compare(b,o.b);
		}
		@Override
		public int compare(tup o1, tup o2) {
			return Integer.compare(o1.b, o2.b);
		}
		
		@Override
	    public int hashCode() {
			return Objects.hash(a, b);
	    }
 
	    @Override
	    public boolean equals(Object obj) {
	    	if (this == obj)
                return true;
	    	if (obj == null)
                return false;
	    	if (getClass() != obj.getClass())
                return false;
	    	tup other = (tup) obj;
	    	return a==other.a && b==other.b;
	    }
	    
	    @Override
	    public String toString() {
	    	return a + " " + b;
	    }
	}
	
	static void shuffle(int[] a) {
		Random get = new Random();
		for (int i = 0; i < a.length; i++) {
			int r = get.nextInt(a.length);
			int temp = a[i];
			a[i] = a[r];
			a[r] = temp;
		}
	}

	static void shuffle(long[] a) {
		Random get = new Random();
		for (int i = 0; i < a.length; i++) {
			int r = get.nextInt(a.length);
			long temp = a[i];
			a[i] = a[r];
			a[r] = temp;
		}
	}

	static class FastReader {
		BufferedReader br;
		StringTokenizer st;

		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		public FastReader(String s) throws FileNotFoundException {
			br = new BufferedReader(new FileReader(new File(s)));
		}

		String next() {
			while (st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}

		int nextInt() {
			return Integer.parseInt(next());
		}

		long nextLong() {
			return Long.parseLong(next());
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}

		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (IOException e) {
				e.printStackTrace();
			}
			return str;
		}
	}
	
	static void dbg(int[] arr) {
		System.out.println(Arrays.toString(arr));
	}
	static void dbg(long[] arr) {
		System.out.println(Arrays.toString(arr));
	}
	static void dbg(boolean[] arr) {
		System.out.println(Arrays.toString(arr));
	}

	static void dbg(Object... args) {
        for (Object arg : args)
            System.out.print(arg + " ");
        System.out.println();
    }
	
	static int[] readArray(int size, FastReader in) {
		int[] a = new int[size];
		for(int i = 0; i < size; i++) {
			a[i] = in.nextInt();
		}
		return a;
	}
	
	static long[] readLongArray(int size, FastReader in) {
		long[] a = new long[size];
		for(int i = 0; i < size; i++) {
			a[i] = in.nextLong();
		}
		return a;
	}
}