CF1696G.Fishingprince Plays With Array Again

Suppose you are given a 1-indexed sequence $a$ of non-negative integers, whose length is $n$, and two integers $x$, $y$. In consecutive $t$ seconds ($t$ can be any positive real number), you can do one of the following operations:

• Select $1\le i \lt n$, decrease $a_i$ by $x\cdot t$, and decrease $a_{i+1}$ by $y\cdot t$.
• Select $1\le i \lt n$, decrease $a_i$ by $y\cdot t$, and decrease $a_{i+1}$ by $x\cdot t$.

Define the minimum amount of time (it might be a real number) required to make all elements in the sequence less than or equal to $0$ as $f(a)$.

For example, when $x=1$, $y=2$, it takes $3$ seconds to deal with the array $[3,1,1,3]$. We can:

• In the first $1.5$ seconds do the second operation with $i=1$.
• In the next $1.5$ seconds do the first operation with $i=3$.

We can prove that it's not possible to make all elements less than or equal to $0$ in less than $3$ seconds, so $f([3,1,1,3])=3$.

Now you are given a 1-indexed sequence $b$ of positive integers, whose length is $n$. You are also given positive integers $x$, $y$. Process $q$ queries of the following two types:

• 1 k v: change $b_k$ to $v$.
• 2 l r: print $f([b_l,b_{l+1},\dots,b_r])$.

假设你有一个从 1 开始编号的非负整数序列 $a$，其长度为 $n$，以及两个整数 $x$、$y$。在连续的 $t$ 秒内（$t$ 可为任意正实数），你可以执行以下两种操作之一：

• 选择满足 $1\le i \lt n$ 的下标 $i$，将 $a_i$ 减少 $x\cdot t$，同时将 $a_{i+1}$ 减少 $y\cdot t$；
• 选择满足 $1\le i \lt n$ 的下标 $i$，将 $a_i$ 减少 $y\cdot t$，同时将 $a_{i+1}$ 减少 $x\cdot t$。

定义使序列中所有元素均小于等于 $0$ 所需的最少时间（该时间可能为实数）为 $f(a)$。

例如，当 $x=1$、$y=2$ 时，处理数组 $[3,1,1,3]$ 需要 $3$ 秒。具体方案如下：

• 前 $1.5$ 秒对 $i=1$ 执行第二种操作；
• 接下来的 $1.5$ 秒对 $i=3$ 执行第一种操作。

可以证明，无法在少于 $3$ 秒内使所有元素 $\le 0$，因此 $f([3,1,1,3])=3$。

现在给你一个从 1 开始编号的正整数序列 $b$，其长度为 $n$，以及正整数 $x$、$y$。你需要处理 $q$ 个查询，查询分为以下两类：

• 1 k v：将 $b_k$ 修改为 $v$；
• 2 l r：输出 $f([b_l,b_{l+1},\dots,b_r])$。

The first line of input contains two integers $n$ and $q$ ($2\le n\le 2\cdot 10^5$, $1\le q\le 2\cdot 10^5$).

The second line of input contains two integers $x$ and $y$ ($1\le x,y\le 10^6$).

The third line of input contains $n$ integers $b_1,b_2,\ldots,b_n$ ($1\le b_i\le 10^6$).

This is followed by $q$ lines. Each of these $q$ lines contains three integers. The first integer $op$ is either $1$ or $2$.

• If it is $1$, it is followed by two integers $k$, $v$ ($1\le k\le n$, $1\le v\le 10^6$). It means that you should change $b_k$ to $v$.
• If it is $2$, it is followed by two integers $l$, $r$ ($1\le l \lt r\le n$). It means that you should print $f([b_l,b_{l+1},\dots,b_r])$.

输入的第一行包含两个整数 $n$ 和 $q$（$2\le n\le 2\cdot 10^5$，$1\le q\le 2\cdot 10^5$）。

输入的第二行包含两个整数 $x$ 和 $y$（$1\le x,y\le 10^6$）。

输入的第三行包含 $n$ 个整数 $b_1,b_2,\ldots,b_n$（$1\le b_i\le 10^6$）。

接下来是 $q$ 行。每行包含三个整数。第一个整数 $op$ 为 $1$ 或 $2$。

• 若 $op=1$，则其后跟两个整数 $k$、$v$（$1\le k\le n$，$1\le v\le 10^6$），表示将 $b_k$ 修改为 $v$。
• 若 $op=2$，则其后跟两个整数 $l$、$r$（$1\le l \lt r\le n$），表示输出 $f([b_l,b_{l+1},\dots,b_r])$。

For each query of type $2$, print one real number — the answer to the query. Your answer is considered correct if its absolute error or relative error does not exceed $10^{-9}$.

对于每个类型为 $2$ 的查询，输出一个实数——该查询的答案。若您的答案的绝对误差或相对误差不超过 $10^{-9}$，则视为正确。

Let's analyse the sample.

In the first query, we are asked to compute $f([3,1,1,4])$. The answer is $3.5$. One optimal sequence of operations is:

• In the first $1.5$ seconds do the second operation with $i=1$.
• In the next $2$ seconds do the first operation with $i=3$.

In the third query, we are asked to compute $f([1,1,1])$. The answer is $1$. One optimal sequence of operations is:

• In the first $0.5$ seconds do the second operation with $i=1$.
• In the next $0.5$ seconds do the first operation with $i=2$.

我们来分析样例。

在第一个查询中，我们需要计算 $f([3,1,1,4])$。答案为 $3.5$。一种最优的操作序列如下：

• 前 $1.5$ 秒执行第二种操作，其中 $i=1$；
• 接下来的 $2$ 秒执行第一种操作，其中 $i=3$。

在第三个查询中，我们需要计算 $f([1,1,1])$。答案为 $1$。一种最优的操作序列如下：

• 前 $0.5$ 秒执行第二种操作，其中 $i=1$；
• 接下来的 $0.5$ 秒执行第一种操作，其中 $i=2$。