Expected Maximum Note Tone

You are given n notes whose sound quality is described by a sequence \(\{a_i\}_{i=1}^n\). There are also n magical spells. The i^th spell increases \(a_i\) by \(s\) (with \(s > 0\)) if the spell succeeds. Each spell works independently with a success probability of \(\frac{p}{q}\). After applying the spells, each note \(i\) will have a value of either \(a_i\) (if the spell fails) or \(a_i+s\) (if the spell succeeds).

Let \(X_i = a_i + s \cdot B_i\), where \(B_i\) is an indicator random variable that is 1 with probability \(\frac{p}{q}\) and 0 otherwise. Your task is to calculate the expected value of the maximum note tone, i.e., find \(E\left[\max_{1 \le i \le n} X_i\right].\)

Special Judge: This problem has a special judge. You can output your answer in one of two ways (see the Output Format section):

1. Option 1: A floating-point number. Your answer is considered correct if its absolute or relative error does not exceed \(10^{-6}\).
2. Option 2: Two integers representing the numerator and denominator of the answer expressed as an irreducible fraction.

Note that if you choose Option 2, the fraction must be in its simplest form.

Mathematical Details:

For each note \(i\), the final value is either \(a_i\) (with probability \(1-\frac{p}{q}\)) or \(a_i+s\) (with probability \(\frac{p}{q}\)). The set of all possible outcomes for each note is \(\{a_i, a_i+s\}\). Thus, the maximum overall has a discrete distribution over the sorted set of candidates \[ S = \{a_i \mid 1 \le i \le n\} \cup \{a_i+s \mid 1 \le i \le n\}. \] For any candidate value \(v\), define \[ F(v)=\prod_{i=1}^{n} f_i(v), \quad \text{where}\quad f_i(v)=\begin{cases} 0, & v<a_i,\\ \;1-\frac{p}{q}, & a_i\le v<a_i+s,\\ 1, & v\ge a_i+s.\end{cases} \] Then the probability that the maximum equals \(v\) is given by \(F(v)-F(v^-)\), where \(F(v^-)\) is the limit from the left. The expected maximum is computed as \[ E[\max_{1\le i\le n}X_i] = \sum_{v\in S} v \cdot \Bigl(F(v)-\lim_{u\to v^-}F(u)\Bigr). \]

inputFormat

The input consists of two lines:

1. The first line contains four integers: n s p q where n is the number of notes, s is the increase value for a successful spell (\(s>0\)), and p and q describe the success probability \(\frac{p}{q}\) of each spell.
2. The second line contains n integers: a1 a2 ... an, representing the initial sound quality of each note.

It is guaranteed that all input values are valid and follow the constraints.

outputFormat

Output the expected maximum note tone after applying the spells. You may output the answer in one of the following two ways:

1. A floating-point number; your answer is accepted if its absolute or relative error does not exceed \(10^{-6}\).
2. Two integers representing the numerator and denominator of the irreducible fraction equal to the expected value.

Note: If you choose the second output format, the fraction must be simplified to its lowest terms.

sample

2 10 1 2
1 2

9.25