Expected Rounds to Reach Zero

We are given (m+1) numbers. The first number has an initial value (p) and is bounded between (0) (the minimum) and (n) (the maximum). The remaining (m) numbers are unbounded (they have no minimum or maximum value).

In each round, you perform the following two operations sequentially:

1. Addition Step: Among all numbers that are not equal to the maximum (n) (i.e. those that can be increased), choose one uniformly at random and increase it by (1).

2. Subtraction Step: Repeat (k) times: among all numbers that are not equal to the minimum (0) (i.e. those that can be decreased), choose one uniformly at random and decrease it by (1).

The task is to compute the expected number of rounds required for the first number to become (0) (i.e. reach the minimum value).

(\textbf{Note:}) In order to simplify the analysis, observe that the other (m) numbers (being unbounded) do not affect the absorption of the first number. In each round, as long as the first number is strictly between (0) and (n), the first number can be increased in the addition step with probability (1/(m+1)) (provided it is less than (n)) and can be decreased in the subtraction step. In the subtraction step, each of the (k) sub-steps chooses the first number with probability (1/(m+1)) provided it is greater than (0) at that moment. Thus, when (p) is sufficiently large relative to (k) so that hitting (0) does not occur in the middle of a round (and assuming (p<n)), an approximate net change in one round is [ \Delta = \frac{1}{m+1} - \frac{k}{m+1} = -\frac{k-1}{m+1}. ] This suggests that if (k > 1) (i.e. the drift is negative) the expected number of rounds is given by [ E = \frac{p (m+1)}{k-1} \quad \text{(if } p>0\text{)}. ] If (p=0) then no rounds are needed, and if (k = 1) then the process is balanced and the first number will never reach 0 (in expectation), so you should output (-1).

inputFormat

Input consists of four integers (m), (n), (p) and (k) separated by spaces, where:

• \(0 \le p \le n \le 10^6\)
• \(1 \le m \le 10^6\)
• \(k\) is a positive integer.

If \(p = 0\), then the expected number of rounds is \(0\). If \(k = 1\) and \(p > 0\), then output \(-1\) to indicate that the first number will never reach \(0\) in expectation.

outputFormat

Output a single number: the expected number of rounds required for the first number to become (0). Your answer is accepted if its absolute error does not exceed (10^{-6}).

sample

2 10 5 3

7.5