Memory and Casinos

题意翻译

现有一排 $n$ 个赌场。 Memory 在第 $i$ 个赌场时有 $p_i$ 的几率获胜并移动到第 $i+1$ 个赌场，如果 $i=n$ 则 Memory 会离开赌场；同时有 $1-p_i$的概率失败并移动到第 $i-1$ 个赌场，如果$i=1$ 则 Memory 会离开赌场。 定义 Memory "掌控"一段区间 $[i,j]$ 当且仅当 Memory 完成以下过程： - Memory 从 $i$ 号赌场出发； - Memory 从未在 $i$ 号赌场失败； - Memory 某一次在 $j$ 号赌场获胜并离开。 现在有 $q$ 次操作，操作有以下两种： - $1\ i\ a\ b$：令$p_i = \frac{a}{b}$； - $2\ l\ r$：询问 Memory "掌控"区间 $[l,r]$ 的概率。 保证在任意时刻 $p_i$ 构成的序列是单调不降的。

题目描述

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!

输入输出格式

输入格式

The first line of the input contains two integers $ n $ and $ q $ ( $ 1<=n,q<=100000 $ ), — number of casinos and number of requests respectively. The next $ n $ lines each contain integers $ a_{i} $ and $ b_{i} $ ( $ 1<=a_{i}&lt;b_{i}<=10^{9} $ ) —  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&lt;b<=10^{9} $ , $ 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.

输出格式

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} $ .

输入输出样例

输入样例 #1

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

输出样例 #1

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