Problem: Piglet has got a birthday today. His friend Winnie the Pooh wants to make the best present for him — a honey pot. Of course Winnie realizes that he won't manage to get the full pot to Piglet. In fact, he is likely to eat all the honey from the pot. And as soon as Winnie planned a snack on is way, the pot should initially have as much honey as possible. 

The day before Winnie the Pooh replenished his honey stocks. Winnie-the-Pooh has n shelves at home, each shelf contains some, perhaps zero number of honey pots. During the day Winnie came to the honey shelves q times; on the i-th time he came to some shelf ui, took from it some pots ki, tasted the honey from each pot and put all those pots on some shelf vi. As Winnie chose the pots, he followed his intuition. And that means that among all sets of ki pots on shelf ui, he equiprobably chooses one.

Now Winnie remembers all actions he performed with the honey pots. He wants to take to the party the pot he didn't try the day before. For that he must know the mathematical expectation of the number m of shelves that don't have a single untasted pot. To evaluate his chances better, Winnie-the-Pooh wants to know the value m after each action he performs.

Your task is to write a program that will find those values for him.

Input

The first line of the input contains a single number n (1 ≤ n ≤ 105) — the number of shelves at Winnie's place. The second line contains n integers ai (1 ≤ i ≤ n, 0 ≤ ai ≤ 100) — the number of honey pots on a shelf number i. 

The next line contains integer q (1 ≤ q ≤ 105) — the number of actions Winnie did the day before. Then follow q lines, the i-th of them describes an event that follows chronologically; the line contains three integers ui, vi and ki (1 ≤ ui, vi ≤ n, 1 ≤ ki ≤ 5) — the number of the shelf from which Winnie took pots, the number of the shelf on which Winnie put the pots after he tasted each of them, and the number of the pots Winnie tasted, correspondingly.

Consider the shelves with pots numbered with integers from 1 to n. It is guaranteed that Winnie-the-Pooh Never tried taking more pots from the shelf than it has.

Output

For each Winnie's action print the value of the mathematical expectation m by the moment when this action is performed. The relative or absolute error of each value mustn't exceed 10 - 9.

Examples

Input

3
2 2 3
5
1 2 1
2 1 2
1 2 2
3 1 1
3 2 2


Output

0.000000000000
0.333333333333
1.000000000000
1.000000000000
2.000000000000

Solution (in JAVA):

Solution:
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.io.BufferedWriter;
import java.util.InputMismatchException;
import java.util.HashMap;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.Writer;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author BSRK Aditya (bsrkaditya@gmail.com)
 */
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);
		TaskC solver = new TaskC();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskC {


    public static long [][] bin = new long[500000][6];

    public void solve(int testNumber, InputReader in, OutputWriter out) {

        for(int i = 0; i < 500000; ++i) Arrays.fill(bin[i], -1);

        int n = in.readInt();
        Expectation [] shelfs = new Expectation[n];
        for(int i = 0; i < n; ++i) {
            int sz = in.readInt();
            shelfs[i] = new Expectation(sz);
        }

        double op = 0;
        for(int i = 0; i < n; ++i) if(shelfs[i].containsKey(0)) op += shelfs[i].get(0);
        int q = in.readInt();
        while(q-- > 0) {
            int u = in.readInt()-1;
            int v = in.readInt()-1;
            int k = in.readInt();
            if(shelfs[u].containsKey(0)) op -= shelfs[u].get(0);
            shelfs[u] = shelfs[u].remove(k);
            if(shelfs[u].containsKey(0)) op += shelfs[u].get(0);
            shelfs[v].add(k);

            out.printLine(op);
        }
    }

    public static long comb(int a, int b) {
        if(bin[a][b] == -1) {
        long ans = 1;
        for(int i = 0; i < b; ++i) ans *= (a-i);
        for(int i = 1; i <= b; ++i) ans /= i;
            bin[a][b] = ans;
        }
        return bin[a][b];
    }
}

class Expectation extends HashMap<Integer, Double> {
    int S;

    public Expectation(int x) {
        S = x;
        put(x, 1.0);
    }

    public void add(int x) {
        S += x;
    }

    public Expectation remove(int x) {
       Expectation ans = new Expectation(S-x);
       ans.clear();

       for(int t = 0; t <= ans.S; ++t) {
           int u = ans.S - t;
           double v = 0;
           for(int z1 = 0; z1 <= x; ++z1) {
               if(containsKey(u+z1)) {
                  int z2 = x - z1;
                  v += get(u+z1)*TaskC.comb(u+z1,z1)*TaskC.comb(t+z2,z2);
               }
           }
           v /= TaskC.comb(S,x);
           if(v != 0.0)
              ans.put(u, v);
       }

       return ans;
    }
}

class InputReader {

    private InputStream stream;
    private byte[] buf = new byte[1024];
    private int curChar;
    private int numChars;
    private SpaceCharFilter filter;

    public InputReader(InputStream stream) {
        this.stream = stream;
    }

    public int read() {
        if (numChars == -1)
            throw new InputMismatchException();
        if (curChar >= numChars) {
            curChar = 0;
            try {
                numChars = stream.read(buf);
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            if (numChars <= 0)
                return -1;
        }
        return buf[curChar++];
    }


    public int readInt() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        int res = 0;
        do {
            if (c < '0' || c > '9')
                throw new InputMismatchException();
            res *= 10;
            res += c - '0';
            c = read();
        } while (!isSpaceChar(c));
        return res * sgn;
    }

    public boolean isSpaceChar(int c) {
        if (filter != null)
            return filter.isSpaceChar(c);
        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }

    public interface SpaceCharFilter {
        public boolean isSpaceChar(int ch);
    }
}

class OutputWriter {
    private final PrintWriter writer;

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

    public OutputWriter(Writer writer) {
        this.writer = new PrintWriter(writer);
    }

    public void print(Object...objects) {
        for (int i = 0; i < objects.length; i++) {
            if (i != 0)
                writer.print(' ');
            writer.print(objects[i]);
        }
    }

    public void printLine(Object...objects) {
        print(objects);
        writer.println();
    }

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

}