有 n 个赌场排成一排。如果 Memory 在赌场 i 玩游戏,他有概率 pi 获胜并移至右侧赌场 (i + 1) 或退出该行(如果 i = n),并且有概率 1 - pi 输并移至左侧赌场 (i - 1) 或退出该行(如果 i = 1)。
如果他完成一次步行,我们就说记忆在区间 i... j 上占主导地位,
- 他从赌场 i 开始。
- 他在赌场从来没有输过。
- 他在赌场 j 中获胜,结束了他的步行。
请注意,内存仍然可以走在第 1 个赌场的左侧和赌场 n 的右侧,并且始终会完成该过程。
现在内存有一些请求,采用以下形式之一:
- 1 i a b:设置$$p_i = \frac{a}{b}$$。
- 2 l r:打印 Memory 在区间 l...r 上占主导地位的概率,即计算 Memory 在赌场 r 获胜后首先离开分段 l...r 的概率,如果她从赌场 l 开始。
保证在任何时刻 p 都是非递减序列,即对于从 1 到 n - 1 的所有 i,pi ≤ pi + 1。
请帮助记忆满足他的所有请求!
输入
输入的第一行包含两个整数 n 和 q(1 ≤ n, q ≤ 100 000), — 分别是赌场数量和请求数量。
接下来的 n 行每行包含整数 ai 和 bi (1 ≤ ai < bi ≤ 109) — $$\frac{a_{i}}{b_{i}}$$ 是在赌场 i 获胜的概率 pi。
接下来的 q 行每行包含上述指定类型之一的查询(1 ≤ a < b ≤ 109、1 ≤ i ≤ n、1 ≤ l ≤ r ≤ n)。
保证至少有一个类型 2 的查询,即输出非空。另外,保证p始终形成非递减序列。
输出
为类型 2 的每个请求打印一个实数 - 男孩在该时间间隔内“占主导地位”的概率。如果绝对误差不超过 10 - 4,您的答案将被视为正确。
即:假设你的答案之一是a,陪审团相应的答案是b。如果|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