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.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        ConsoleIO io = new ConsoleIO();
        new Main(io).solve();
        io.close();
    }

    ConsoleIO io;

    Main(ConsoleIO io) {
        this.io = io;
    }

    long MOD = 1_000_000_007;
    int N, M, Q;


    int mid;
    double[][] tree;

    public void solve() {
        N = io.ri();

        int treeSize = N;
        while (treeSize != (treeSize & -treeSize))
            treeSize += treeSize & -treeSize;
        mid = treeSize;
        treeSize <<= 1;
        tree = new double[treeSize][2];

        int Q = io.ri();
        int k = mid;
        for(int i = 0;i<N;i++) {
            int a = io.ri();
            int b = io.ri();
            tree[k][0] = a*1.0/ b;
            tree[k++][1] = (b-a)*1.0/ b;
        }
        for (int i = treeSize - 1; i > 0; i -= 2)
        {
            double[] a = tree[i];
            double[] b = tree[i - 1];
            tree[i >> 1] = aggregate(b, a);
        }

        StringBuilder res = new StringBuilder();
        for(int i =0;i<Q;i++){
            int t = io.ri();
            if(t==1){
                int idx = io.ri();
                int a = io.ri();
                int b = io.ri();
                double v = a*1.0/ b;
                update(idx-1, v);
            }else{
                int left = io.ri();
                int right = io.ri();
                double v = query(left-1,right-1);
                if(res.length()>0)res.append(System.lineSeparator());
                res.append(v);
            }
        }
        io.writeLine(res.toString());
    }

    double[] aggregate(double[] a, double[] b){
        double[] res = new double[2];
        double ac0 = (1-a[1])*b[0]/(1-(1-a[1])*(1-b[0]));
        double ac1 = (1-b[0])*a[1]/(1-(1-b[0])*(1-a[1]));
        res[0] = a[0]*(b[0]+(1-b[0])*ac0);
        res[1] = b[1]*(a[1]+(1-a[1])*ac1);
        return res;
    }
    public void update(int idx, double value)
    {
        idx += mid;
        tree[idx][0] = value;
        tree[idx][1] = 1-value;
        while (idx > 1)
        {
            int parent = idx >> 1;
            tree[parent] = (idx&1)==0?aggregate(tree[idx], tree[idx + 1]):aggregate(tree[idx - 1], tree[idx]);
            idx = parent;
        }
    }
    public double query(int left, int right)
    {
        left += mid;
        right += mid;
        if (left == right)
            return tree[left][0];
        double[] resL = tree[left];
        double[] resR = tree[right];
        while (left + 1 < right)
        {
            if ((left & 1) == 0)
                resL = aggregate(resL, tree[left + 1]);
            if ((right & 1) == 1)
                resR = aggregate(tree[right - 1], resR);
            left >>= 1;
            right >>= 1;
        }

        return aggregate(resL, resR)[0];
    }
}

class ConsoleIO {
    BufferedReader br;
    PrintWriter out;
    public ConsoleIO(){br = new BufferedReader(new InputStreamReader(System.in));out = new PrintWriter(System.out);}
    public void flush(){this.out.flush();}
    public void close(){this.out.close();}
    public void writeLine(String s) {this.out.println(s);}
    public void writeInt(int a) {this.out.print(a);this.out.print(' ');}
    public void writeWord(String s){
        this.out.print(s);
    }
    public void writeIntArray(int[] a, int k, String separator) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < k; i++) {
            if (i > 0) sb.append(separator);
            sb.append(a[i]);
        }
        this.writeLine(sb.toString());
    }
    public int read(char[] buf, int len){try {return br.read(buf,0,len);}catch (Exception ex){ return -1; }}
    public String readLine() {try {return br.readLine();}catch (Exception ex){ return "";}}
    public long[] readLongArray() {
        String[]n=this.readLine().trim().split("\\s+");long[]r=new long[n.length];
        for(int i=0;i<n.length;i++)r[i]=Long.parseLong(n[i]);
        return r;
    }
    public int[] readIntArray() {
        String[]n=this.readLine().trim().split("\\s+");int[]r=new int[n.length];
        for(int i=0;i<n.length;i++)r[i]=Integer.parseInt(n[i]);
        return r;
    }
    public int[] readIntArray(int n) {
        int[] res = new int[n];
        char[] all = this.readLine().toCharArray();
        int cur = 0;boolean have = false;
        int k = 0;
        boolean neg = false;
        for(int i = 0;i<all.length;i++){
            if(all[i]>='0' && all[i]<='9'){
                cur = cur*10+all[i]-'0';
                have = true;
            }else if(all[i]=='-') {
                neg = true;
            }
            else if(have){
                res[k++] = neg?-cur:cur;
                cur = 0;
                have = false;
                neg = false;
            }
        }
        if(have)res[k++] = neg?-cur:cur;
        return res;
    }
    public int ri() {
        try {
            int r = 0;
            boolean start = false;
            boolean neg = false;
            while (true) {
                int c = br.read();
                if (c >= '0' && c <= '9') {
                    r = r * 10 + c - '0';
                    start = true;
                } else if (!start && c == '-') {
                    start = true;
                    neg = true;
                } else if (start || c == -1) return neg ? -r : r;
            }
        } catch (Exception ex) {
            return -1;
        }
    }
    public long readLong() {
        try {
            long r = 0;
            boolean start = false;
            boolean neg = false;
            while (true) {
                int c = br.read();
                if (c >= '0' && c <= '9') {
                    r = r * 10 + c - '0';
                    start = true;
                } else if (!start && c == '-') {
                    start = true;
                    neg = true;
                } else if (start || c == -1) return neg ? -r : r;
            }
        } catch (Exception ex) {
            return -1;
        }
    }
    public String readWord() {
        try {
            boolean start = false;
            StringBuilder sb = new StringBuilder();
            while (true) {
                int c = br.read();
                if (c!= ' ' && c!= '\r' && c!='\n' && c!='\t') {
                    sb.append((char)c);
                    start = true;
                } else if (start || c == -1) return sb.toString();
            }
        } catch (Exception ex) {
            return "";
        }
    }
    public char readSymbol() {
        try {
            while (true) {
                int c = br.read();
                if (c != ' ' && c != '\r' && c != '\n' && c != '\t') {
                    return (char) c;
                }
            }
        } catch (Exception ex) {
            return 0;
        }
    }
    public char readChar(){try {return (char)br.read();}catch (Exception ex){ return 0; }}
}
class Pair {
    public Pair(int a, long b) {this.a = a;this.b = b;}
    public int a;
    public long b;
}
class Tri {
    public Tri(int a, int b, int c) {this.a = a;this.b = b;this.c = c;}
    public int a;
    public int b;
    public int c;
}
class PairLL {
    public PairLL(long a, long b) {this.a = a;this.b = b;}
    public long a;
    public long b;
}