Збір рюкзаків
Завдання Джеральда — зустрічати команди 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.