Knapsack Collection

Gerald welcomes the teams arriving for a programming contest at the airport. One of his duties is to stand at the luggage carousel and collect every knapsack the teams bring. Gerald is a lazy person, so he stays at one position of the carousel and waits for bags to pass by so he can pick them up.

The carousel consists of $s$ luggage slots, numbered in ascending order from $0$ to $s-1$. The carousel is cyclic, so slots $s-1$ and $0$ lie side by side as well. It turns so that if Gerald stands in front of slot $i$ at some point in time, he stands in front of slot $(i+1) \bmod s$ one time unit later.

In the beginning Gerald prepares a huge baggage cart at some slot and stands there to wait for luggage. When a knapsack arrives in front of him, he needs $t$ time units to take it and put it on the cart. After these $t$ time units he is ready to pick up another knapsack. As long as knapsacks remain on the carousel, Gerald takes the next one to arrive at his position once he is ready.

Gerald wonders how his choice of position changes the time the task takes. There are $s$ slots that can appear in front of him after the preparation. Compute the minimum, the maximum, and the average time needed to pick up all knapsacks, taken over those $s$ slots. Time starts when he has prepared the cart at some slot and ends when he has put the last knapsack on the cart.

The first line contains three integers $n$, $s$ and $t$ ($1 \le n \le 2000$, $1 \le s \le 10^7$, $1 \le t \le 10^7$), where $n$ is the number of knapsacks to pick up, $s$ is the number of slots of the carousel, and $t$ is the number of time units Gerald needs to take one knapsack from the carousel and put it on the cart.

The second line contains $n$ integers $k_1, \ldots, k_n$ ($0 \le k_i \le s-1$), the slots of the knapsacks.

Several knapsacks may be stacked on top of each other in the same slot, but Gerald still picks up only one knapsack at a time.

Print three lines: the minimum time, the maximum time, and the average time over all $s$ starting slots.

Print the average as a reduced fraction p/q, where $q \ge 1$ and the greatest common divisor of $p$ and $q$ is $1$. When the average is an integer, print it with denominator $1$, for example 16/1.