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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.io.BufferedWriter;
import java.io.IOException;
import java.util.InputMismatchException;
import java.util.ArrayList;
import java.util.stream.DoubleStream;
import java.util.List;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Ben King
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        OutputWriter out = new OutputWriter(outputStream);
        DInterstellarBattle solver = new DInterstellarBattle();
        solver.solve(1, in, out);
        out.close();
    }

    static class DInterstellarBattle {
        int N;
        int[] parent;
        List<List<Integer>> bullshit;

        public void solve(int testNumber, InputReader in, OutputWriter out) {
            N = in.nextInt();
            double[] P = new double[N];
            bullshit = new ArrayList<>();
            for (int i = 0; i < N; i++) bullshit.add(new ArrayList<>());
            parent = new int[N];
            for (int i = 0; i < N; i++) P[i] = 1.0 - in.nextDouble();
            List<List<Integer>> graph = new ArrayList<>();
            for (int i = 0; i < N; i++) graph.add(new ArrayList<>());
            for (int i = 0; i < N - 1; i++) {
                int u = in.nextInt();
                int v = in.nextInt();
                graph.get(u).add(v);
                graph.get(v).add(u);
            }
            int Q = in.nextInt();

            double[] values = new double[N];
            dfs(0, graph, P, -1, values);
            double sum = Arrays.stream(values).sum();

            for (int t = 0; t < Q; t++) {
                int i = in.nextInt();
                double qv = 1.0 - in.nextDouble();

                sum -= P[i] * (parent[i] == -1 ? 1.0 : (1.0 - P[parent[i]]));
                for (int j : bullshit.get(i))
                    sum -= P[j] * (parent[j] == -1 ? 1.0 : (1.0 - P[parent[j]]));
                P[i] = qv;
                sum += P[i] * (parent[i] == -1 ? 1.0 : (1.0 - P[parent[i]]));
                for (int j : bullshit.get(i))
                    sum += P[j] * (parent[j] == -1 ? 1.0 : (1.0 - P[parent[j]]));
                out.println(sum);
            }

            out.flush();
        }

        void dfs(int index, List<List<Integer>> graph, double[] P, int from, double[] answers) {
            double prob = P[index] * (from == -1 ? 1.0 : (1.0 - P[from]));
            answers[index] = prob;
            parent[index] = from;
            for (int neighbor : graph.get(index)) {
                if (neighbor == from) continue;
                bullshit.get(index).add(neighbor);
                dfs(neighbor, graph, P, index, answers);
            }
        }

    }

    static class OutputWriter {
        private final PrintWriter writer;

        public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(
                outputStream)));
        }

        public OutputWriter(java.io.Writer outputStreamWriter) {
            writer = new PrintWriter(new BufferedWriter(outputStreamWriter));
        }

        public void flush() {
            writer.flush();
        }

        public void close() {
            writer.flush();
            writer.close();
        }

        public void println(double i) {
            writer.println(i);
        }

    }

    static class InputReader {
        private static final int DEFAULT_BUFFER_SIZE = 1 << 16;
        private static final InputStream DEFAULT_STREAM = System.in;
        private int c;
        private byte[] buf;
        private int bufferSize;
        private int bufIndex;
        private int numBytesRead;
        private InputStream stream;
        private static final byte EOF = -1;
        private static final byte SPACE = 32;
        private static final byte DASH = 45;
        private char[] charBuffer;
        private static byte[] bytes = new byte[58];
        private static int[] ints = new int[58];
        private static char[] chars = new char[128];

        static {
            char ch = ' ';
            int value = 0;
            byte _byte = 0;
            for (int i = 48; i < 58; i++) bytes[i] = _byte++;
            for (int i = 48; i < 58; i++) ints[i] = value++;
            for (int i = 32; i < 128; i++) chars[i] = ch++;
        }

        public InputReader() {
            this(DEFAULT_STREAM, DEFAULT_BUFFER_SIZE);
        }

        public InputReader(int bufferSize) {
            this(DEFAULT_STREAM, bufferSize);
        }

        public InputReader(InputStream stream) {
            this(stream, DEFAULT_BUFFER_SIZE);
        }

        public InputReader(InputStream stream, int bufferSize) {
            if (stream == null || bufferSize <= 0)
                throw new IllegalArgumentException();
            buf = new byte[bufferSize];
            charBuffer = new char[128];
            this.bufferSize = bufferSize;
            this.stream = stream;
        }

        private int readJunk(int token) {

            if (numBytesRead == EOF) return EOF;

            // Seek to the first valid position index
            do {

                while (bufIndex < numBytesRead) {
                    if (buf[bufIndex] > token) return 0;
                    bufIndex++;
                }

                // reload buffer
                try {
                    numBytesRead = stream.read(buf);
                }
                catch (IOException e) {
                    e.printStackTrace();
                }
                if (numBytesRead == EOF) return EOF;
                bufIndex = 0;

            } while (true);

        }

        public int nextInt() {
            try {
                if (readJunk(DASH - 1) == EOF) throw new IOException();
                int sgn = 1, res = 0;

                c = buf[bufIndex];
                if (c == DASH) {
                    sgn = -1;
                    bufIndex++;
                }

                do {

                    while (bufIndex < numBytesRead) {
                        if (buf[bufIndex] > SPACE) {
                            res = (res << 3) + (res << 1);
                            res += ints[buf[bufIndex++]];
                        }
                        else {
                            bufIndex++;
                            return res * sgn;
                        }
                    }

                    // Reload buffer
                    numBytesRead = stream.read(buf);
                    if (numBytesRead == EOF) return res * sgn;
                    bufIndex = 0;

                } while (true);
            }
            catch (IOException e) {
                e.printStackTrace();
                return -1;
            }

        }

        private void doubleCharBufferSize() {
            char[] newBuffer = new char[charBuffer.length << 1];
            for (int i = 0; i < charBuffer.length; i++) newBuffer[i] = charBuffer[i];
            charBuffer = newBuffer;
        }

        public String next() {
            try {
                if (numBytesRead == EOF) return null;
                if (readJunk(SPACE) == EOF) return null;

                for (int i = 0; ; ) {
                    while (bufIndex < numBytesRead) {
                        if (buf[bufIndex] > SPACE) {
                            if (i == charBuffer.length) doubleCharBufferSize();
                            charBuffer[i++] = (char) buf[bufIndex++];
                        }
                        else {
                            bufIndex++;
                            return new String(charBuffer, 0, i);
                        }
                    }

                    // Reload buffer
                    numBytesRead = stream.read(buf);
                    if (numBytesRead == EOF) return new String(charBuffer, 0, i);
                    bufIndex = 0;
                }
            }
            catch (IOException e) {
                e.printStackTrace();
                return null;
            }
        }

        public double nextDouble() {
            String doubleVal = next();
            if (doubleVal == null) throw new InputMismatchException();
            return Double.valueOf(doubleVal);
        }

    }
}

