CF712E.Memory and Casinos

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 .
• 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!

有 $n$ 家赌场排成一行。若 Memory 在第 $i$ 家赌场进行游戏，则他以概率 $p_i$ 获胜，并移动到右侧的赌场（即第 $i+1$ 家），或直接离开该行（当 $i = n$ 时）；以概率 $1 - p_i$ 失败，并移动到左侧的赌场（即第 $i-1$ 家），或同样离开该行（当 $i = 1$ 时）。

我们称 Memory 支配区间 $i \dots j$，如果他完成如下行走过程：

• 从第 $i$ 家赌场出发；
• 在第 $i$ 家赌场从未失败；
• 最终在第 $j$ 家赌场获胜并结束行走。

注意：Memory 仍可走到第 $1$ 家赌场左侧或第 $n$ 家赌场右侧，且此时过程总是立即终止。

现在 Memory 提出若干请求，每条请求为以下两种形式之一：

• 1 i a b：将 $p_i$ 设置为 $\frac{a}{b}$；
• 2 l r：输出 Memory 支配区间 $l \dots r$ 的概率，即：若 Memory 从第 $l$ 家赌场出发，则他首次离开区间 $l \dots r$ 时恰好是在第 $r$ 家赌场获胜的概率。

保证在任意时刻，序列 $p$ 都是非递减的，即对所有 $i = 1, 2, \dots, n-1$，均有 $p_i \leq p_{i+1}$。

请帮助 Memory 回答所有请求！

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 ≤ 109) — 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 ≤ 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.

输入的第一行包含两个整数 $n$ 和 $q$（$1 \leq n, q \leq 100\,000$），分别表示赌场的数量和查询的数量。

接下来的 $n$ 行，每行包含两个整数 $a_i$ 和 $b_i$（$1 \leq a_i < b_i \leq 10^9$）—— 是在第 $i$ 个赌场获胜的概率 $p_i$。

接下来的 $q$ 行，每行包含上述指定类型之一的查询（$1 \leq a < b \leq 10^9$，$1 \leq i \leq n$，$1 \leq l \leq r \leq n$）。

保证至少存在一个类型为 2 的查询，即输出非空。此外，还保证在任意时刻，概率序列 $p$ 均为非递减序列。

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.

对于每个类型为 2 的查询，请输出一个实数——即该区间内男孩“主导”的概率。若你的答案绝对误差不超过 $10^{-4}$，则视为正确。

具体而言：假设你的某个答案为 $a$，而评测组对应的标准答案为 $b$。当且仅当 $|a - b| \leq 10^{-4}$ 时，评测程序将判定你的答案正确。