There are n casinos lined in a row. If Memory plays at casino i, he has probability p_i to win and move to the casino on the right (i + 1) or exit the row (if i = n), and a probability 1 - p_i 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 $\text{[math]}$ .
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. p_i ≤ p_i + 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 a_i and b_i (1 ≤ a_i < b_i ≤ 10⁹) — $\text{[math]}$ is the probability p_i of winning in casino i.

The next q lines each contain queries of one of the types specified above (1 ≤ a < b ≤ 10⁹, 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.

Idx	Name	Rating
A	Memory and Crow	800
B	Memory and Trident	1100
C	Memory and De-Evolution	1600
D	Memory and Scores	2200
E	Memory and Casinos	2500

Codeforces Round 370 (Div. 2)