Problem: There are n casinos lined in a row. If Memory plays at casino i, he has probability pi to win and move to the casino on the right (i + 1) or exit the row (if i = n), and a probability 1 - pi to lose and move to the casino on the left (i - 1) or also exit the row (if i = 1). 

We say that Memory dominates on the interval i... j if he completes a walk such that,

  * He starts on casino i. 
  * He never looses in casino i. 
  * He finishes his walk by winning in casino j. 



Note that Memory can still walk left of the 1-st casino and right of the casino n and that always finishes the process.

Now Memory has some requests, in one of the following forms:

  * 1 i a b: Set <image>. 
  * 2 l r: Print the probability that Memory will dominate on the interval l... r, i.e. compute the probability that Memory will first leave the segment l... r after winning at casino r, if she starts in casino l. 



It is guaranteed that at any moment of time p is a non-decreasing sequence, i.e. pi ≤ pi + 1 for all i from 1 to n - 1.

Please help Memory by answering all his requests!

Input

The first line of the input contains two integers n and q(1 ≤ n, q ≤ 100 000), — number of casinos and number of requests respectively.

The next n lines each contain integers ai and bi (1 ≤ ai < bi ≤ 109) — <image> is the probability pi of winning in casino i.

The next q lines each contain queries of one of the types specified above (1 ≤ a < b ≤ 109, 1 ≤ i ≤ n, 1 ≤ l ≤ r ≤ n).

It's guaranteed that there will be at least one query of type 2, i.e. the output will be non-empty. Additionally, it is guaranteed that p forms a non-decreasing sequence at all times.

Output

Print a real number for every request of type 2 — the probability that boy will "dominate" on that interval. Your answer will be considered correct if its absolute error does not exceed 10 - 4.

Namely: let's assume that one of your answers is a, and the corresponding answer of the jury is b. The checker program will consider your answer correct if |a - b| ≤ 10 - 4.

Example

Input

3 13
1 3
1 2
2 3
2 1 1
2 1 2
2 1 3
2 2 2
2 2 3
2 3 3
1 2 2 3
2 1 1
2 1 2
2 1 3
2 2 2
2 2 3
2 3 3


Output

0.3333333333
0.2000000000
0.1666666667
0.5000000000
0.4000000000
0.6666666667
0.3333333333
0.2500000000
0.2222222222
0.6666666667
0.5714285714
0.6666666667

Solution (in JAVA):

Solution:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;

public class E {

    private static final boolean TEST_CASES = false;

    private static class Solver {
	    private double[] p;
        void solve(int testCaseNo) {
		int n, q;
		n = IO.nextInt();
		q = IO.nextInt();

		p = new double[n+1];
		for (int i = 1; i <= n; ++i) {
			int a = IO.nextInt(), b = IO.nextInt();
			p[i] = (double)a/(double)b;
		}

		Node tree = create(1, n);


		for (int i = 0; i < q; ++i) {
			int t = IO.nextInt();
			if (t == 1) {
				int id = IO.nextInt(), a = IO.nextInt(), b = IO.nextInt();
				update(id, (double)a/(double)b, tree);
			} else {
				int l = IO.nextInt(), r = IO.nextInt();
				IO.writer.printf("%.5f\n", query(l, r, tree).p);
			}
		}
	}

	private void update(int id, double p, Node n) {

		if ( (n.l == id) && (n.r == id) ) {
			n.p = p;
			n.q = p;
			return ;
		}

		if ( (n.l > id) || (n.r < id) ) {
			return ;
		}

		update(id, p, n.left);
		update(id, p, n.right);

		n.p = calP(n.left, n.right);
		n.q = calQ(n.left, n.right);
	}


	private Node query(int l, int r, Node tree) {

		if ( (tree.l >= l) && (tree.r <= r) ) {
			return tree;
		}

		if ( (tree.l > r) || (tree.r < l) ) {
			return null;
		}

		Node p1 = query(l, r, tree.left);
		Node p2 = query(l, r, tree.right);

		if (p1 == null) return p2;
		if (p2 == null) return p1;

		double p = calP(p1, p2);
		double q = calQ(p1, p2);

		return new Node(p, q, -1, -1, null, null);
	}

	private Node create(int l, int r) {
		if (l == r) {
			return new Node(p[l], p[l], l, r, null, null);
		}

		int m = (l + r) / 2;

		Node n1 = create(l, m);
		Node n2 = create(m+1, r);

		double p = calP(n1, n2);
		double q = calQ(n1, n2);

		return new Node(p, q, l, r, n1, n2);
	}

	private double calP(Node n1, Node n2) {

		return (n1.p * n2.p) / (1 - n1.q + n1.q * n2.p);

	}
	private double calQ(Node n1, Node n2) {

		return n2.q + (n1.q * n2.p * (1 - n2.q)) / (1 + n1.q * (n2.p - 1));

	}

	private class Node {
		double p, q;
		int l, r;
		Node left, right;

		Node(double pi, double qi, int ll, int rr, Node lft, Node rgt) {
			p = pi;
			q = qi;
			l = ll;
			r = rr;
			left = lft;
			right = rgt;
		}
	}
	
    }

    private static class IO {

        private static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        static final PrintWriter writer = new PrintWriter(System.out);

        private static StringTokenizer tokenizer = null;

        static String nextToken() {
            checkTokenizer();
            return tokenizer.nextToken();
        }

        static int nextInt() {
            return Integer.parseInt(nextToken());
        }

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

        private static boolean isTokenizerEmpty() {
            return tokenizer == null || !tokenizer.hasMoreTokens();
        }

        private static void checkTokenizer() {
            while (isTokenizerEmpty()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
        }
    }

    private static void go() {
        int testCases = TEST_CASES ? IO.nextInt() : 1;

        Solver solver = new Solver();
        for (int testCase = 0; testCase < testCases; testCase++) {
            solver.solve(testCase);
        }
    }

    public static void main(String[] args) {
        try {
            go();
        } finally {
            IO.close();
        }
    }
}