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.math.BigInteger;
import java.util.*;
import java.io.*;

public class Main {
    static IO io;
    static int offset;
    static double[][] segment;
    public static void main(String[] args) throws Exception {

        io = new IO(System.in, System.out);
        solve();
        io.close();
    }

    static void solve() {

        int n = io.nextInt();
        int q = io.nextInt();
        offset=1;
        while(offset<n)
            offset<<=1;

        segment=new double[2*offset][2];
        for (int i = 1; i < segment.length; i++) {
            segment[i][0]=1;
            segment[i][1]=1;
        }
        for (int i = 0; i < n; i++) {
            set(i,io.nextDouble()/io.nextDouble());
        }
        for (int i = 0; i <q ; i++) {
            switch(io.nextInt()){
                case 1:
                    set(io.nextInt()-1,io.nextDouble()/io.nextDouble());
                    break;
                case 2:
                    io.println(queryPrint(io.nextInt()-1,io.nextInt()-1));
                    break;
            }
        }

    }
static void set(int idx, double value){
    int i=idx+offset;
    segment[i]=new double[] {value, value};
    for (i >>= 1; i >0 ; i>>=1) {
        segment[i]=combine(segment[i],segment[i<<1],segment[i<<1 | 1]);
    }
}
    static double[] combine(double r[], double[]p1, double[]p2){
        double e21= p2[0]/(1-p1[1]*(1-p2[0]));
        double e11=p1[0]*e21;
        double e22=(1-p2[1])*p1[1]*e21+p2[1];
        r[0]=e11;
        r[1]=e22;
        return r;
    }

    static double queryPrint (int a,int b){
        a+=offset;
        b+=offset;
        double[] L= new double[]{1,0};
        double[] R= new double[] {1,0};
        while(a<b){
            if((a&1)!=0){
                L=combine(L,L,segment[a]);
                a++;
            }
            if((b&1)==0){
                R=combine(R,segment[b],R);
                b--;
            }
            a>>=1;
            b>>=1;
        }
        if(a==b){
            L=combine(L,L,segment[a]);
        }
        L=combine(L,L,R);
        return L[0];
    }



    static class IO extends PrintWriter {
        public IO(InputStream i, OutputStream o) {
            super(new BufferedOutputStream(o));
            r = new BufferedReader(new InputStreamReader(i));
        }

        @Override
        public void println(String a) {
            synchronized (lock) {
                print(a);
                print('\n');
            }
        }

        public boolean hasMoreTokens() {
            return peekToken() != null;
        }

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

        public double nextDouble() {
            return Double.parseDouble(nextToken());
        }

        public long nextLong() {
            return Long.parseLong(nextToken());
        }

        public String next() {
            return nextToken();
        }

        public BigInteger nextBigInteger() {
            return new BigInteger(next());
        }

        public int[] nextIntArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = io.nextInt();
            }
            return a;
        }

        public Integer[] nextIntegerArray(int n) {
            Integer[] a = new Integer[n];
            for (int i = 0; i < n; i++) {
                a[i] = io.nextInt();
            }
            return a;
        }


        private BufferedReader r;
        private String line;
        private StringTokenizer st;
        private String token;

        private String peekToken() {
            if (token == null)
                try {
                    while (st == null || !st.hasMoreTokens()) {
                        line = r.readLine();
                        if (line == null) return null;
                        st = new StringTokenizer(line);
                    }
                    token = st.nextToken();
                } catch (IOException e) {
                }
            return token;
        }

        private String nextToken() {
            String ans = peekToken();
            token = null;
            return ans;
        }
    }
}