배낭 수거

제럴드는 공항에서 프로그래밍 대회 참가 팀을 맞이한다. 맡은 일 가운데 하나는 수하물 컨베이어 앞에 서서 팀들이 부친 배낭을 모두 거두는 것이다. 제럴드는 게으른 사람이라 컨베이어의 한 자리에 계속 서서, 가방이 앞을 지나갈 때 집어 올린다.

컨베이어는 $s$개의 자리로 이루어져 있고 자리마다 $0$부터 $s-1$까지 오름차순으로 번호가 붙어 있다. 컨베이어는 원형이라 자리 $s-1$과 자리 $0$도 서로 붙어 있다. 어느 시각에 제럴드가 자리 $i$ 앞에 있으면 한 시간 단위 뒤에는 자리 $(i+1) \bmod s$ 앞에 있도록 컨베이어가 돈다.

처음에 제럴드는 커다란 수하물 카트를 어느 한 자리에 준비해 두고 그 자리에서 짐을 기다린다. 배낭이 앞에 오면 집어서 카트에 싣는 데 $t$시간 단위가 걸리고, 그 $t$시간 단위가 지나면 다음 배낭을 집을 준비가 끝난다. 컨베이어에 배낭이 남아 있는 한, 제럴드는 준비가 끝난 시점 이후로 가장 먼저 자기 앞에 오는 배낭을 집는다.

제럴드는 자리를 어디로 고르느냐에 따라 일을 끝내는 시간이 얼마나 달라지는지 궁금하다. 준비를 마친 뒤 제럴드 앞에 올 수 있는 자리는 $s$가지이다. 이 $s$가지 자리 전체에 대해 배낭을 모두 거두는 데 걸리는 시간의 최솟값, 최댓값, 평균을 구하라. 시간은 어느 자리에 카트를 준비한 순간 시작해서 마지막 배낭을 카트에 실은 순간 끝난다.

첫째 줄에 세 정수 $n$, $s$, $t$가 주어진다 ($1 \le n \le 2000$, $1 \le s \le 10^7$, $1 \le t \le 10^7$). $n$은 거둘 배낭의 개수, $s$는 컨베이어의 자리 개수, $t$는 배낭 하나를 집어 카트에 싣는 데 걸리는 시간 단위이다.

둘째 줄에 배낭이 놓인 자리를 나타내는 정수 $n$개 $k_1, \ldots, k_n$이 주어진다 ($0 \le k_i \le s-1$).

같은 자리에 배낭이 여러 개 쌓여 있을 수 있지만, 제럴드는 한 번에 하나씩만 집는다.

세 줄을 출력한다. 첫째 줄에 $s$가지 시작 자리 전체에 대한 최소 시간, 둘째 줄에 최대 시간, 셋째 줄에 평균 시간을 출력한다.

평균 시간은 기약분수 p/q 꼴로 출력한다. 여기서 $q \ge 1$이고 $p$와 $q$의 최대공약수는 $1$이다. 평균이 정수이면 분모를 $1$로 두어 16/1처럼 출력한다.