Codeforces Global Round 21 |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

brute force

data structures

geometry

math

*3300

No tag edit access

The problem statement has recently been changed. View the changes.

×
G. Fishingprince Plays With Array Again

time limit per test

6 secondsmemory limit per test

1024 megabytesinput

standard inputoutput

standard outputSuppose 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<n$$$, decrease $$$a_i$$$ by $$$x\cdot t$$$, and decrease $$$a_{i+1}$$$ by $$$y\cdot t$$$.
- Select $$$1\le i<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])$$$.

Input

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<r\le n$$$). It means that you should print $$$f([b_l,b_{l+1},\dots,b_r])$$$.

Output

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

Example

Input

4 3 1 2 3 1 1 4 2 1 4 1 1 1 2 1 3

Output

3.500000000000000 1.000000000000000

Note

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

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/21/2024 03:01:24 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|