Сбор рюкзаков
Задача Джеральда - приветствовать команды NWERC этого года в аэропорту Линчепинга. Одна из его обязанностей - стоять в багажной карусели и собирать все рюкзаки, которые приносят команды. Джеральд ленивый человек, поэтому он просто стоит в одном месте у карусели и ждет, когда мешки пройдут, чтобы их забрать.
Багажная карусель состоит из s багажных отсеков, пронумерованных в порядке возрастания от 0 до s - 1. Поскольку карусель багажа является циклической, багажные отсеки s - 1 и 0 также лежат бок о бок. Карусель поворачивается таким образом, что если Джеральд встанет перед слотом i в какой-то момент времени, то через единицу времени он будет перед слотом (i + 1) mod s.
В начале Джеральд берет огромную багажную тележку и становится в определенном месте, ожидая багаж. Когда рюкзак прибывает перед Джеральдом, ему нужны t единицы времени, чтобы взять его и положить в корзину. После этих единиц времени он готов взять еще один рюкзак. Пока в багажной карусели остаются рюкзаки, Джеральд всегда берет следующий, который доходит до его позиции, причем только тогда когда он уже убрал предыдущий рюкзак.
Теперь Джеральд задается вопросом о влиянии своего выбора позиции на то время, которое понадобится ему для завершения этой задачи. Вам следует помочь Джеральду вычислить минимальное, максимальное и среднее время, за которое можно собрать все ранцы, расположенные по всем возможным слотам, которые могут появиться перед Джеральдом. Время начинается, когда он подготовил багажную тележку в каком-то отсеке багажной карусели и заканчивается после того, как он положил на тележку последний рюкзак.
Входные данные
Состоит из:
строка с тремя целыми числами n (1 ≤ n ≤ 2000), s (1 ≤ s ≤
10^7) и t (1 ≤ t ≤10^7), где n - количество рюкзаков которые следует подобрать, s - число слотов в карусели, t - количество единиц времени, которое требуется Джеральду чтобы взять рюкзак с ленты и положить в тележку;одна строка с n целыми числами
k[1], ...,k[n](0 ≤k[i]≤ s - 1 для 1 ≤ i ≤ n) - слоты с рюкзаками.
В одном и том же слоте друг над другом может быть несколько рюкзаков, но Джеральд все равно может взять только один рюкзак за раз.
Выходные данные
Выведите три строки, содержащие минимальное, максимальное и среднее время, за которое можно забрать весь багаж во всех s позициях. Среднее время следует выводить в виде несократимой дроби p / q.