Задача J. Веселый пир

Во дворе дворца был накрыт большой прямоугольный стол для гостей. Все гости имеют номера от 1 до N, которые были им присвоены при обходе стола по часовой стрелке, считая от точки раздачи (см. рисунок).
Блюда, предложенные гостям, им очень понравились, и они стали просить добавки. На подносе у разносчика блюд помещается T тарелок. Как только набирается T "заявок" на добавку (кроме, быть может, нескольких последних заявок), разносчик действует следующим образом:
- сначала он определяет максимальный и минимальный номера гостей (среди этих T заявок), которые попросили добавки, и вычисляет, до которого из них идти ближе. Если путь одинаков, выбирается гость с меньшим порядковым номером
- после этого разносчик идет сначала к выбранному гостю, а потом обходит остальных гостей, которым он несет добавку, либо в порядке возрастания их номеров (если сначала он пошел к гостю с минимальным номером), либо в порядке убывания их номеров (если сначала он пошел к гостю с максимальным номером).
- когда все блюда розданы, он возвращается к точке раздачи вдоль стола более коротким путем.
По заданной последовательности гостей, попросивших добавки, определите, какой процент от пройденного пути разносчики ходили с пустыми подносами, если все заявки были удовлетворены.

Формат входного файла input.txt
Первая строка - целые числа N, T, d, L через пробел, где N (2 <= N <= 10000, N - четное)- количество гостей, T (1 <= T <= 1000) - количество тарелок, помещающихся на подносе, d (1 <= d <= 10) - расстояние между гостями (см. рисунок), L - количество поступивших заявок на добавку (1 <= L <= 100000)
В следующих строках содержатся через пробел номера гостей (числа от 1 до N) в той последовательности, в которой они обращались за добавками (по 100 номеров в каждой строке, за исключением, быть может, последней строки).

Формат выходного файла output.txt
Первая строка - вещественное число с точностью 4 знака после запятой - процент "холостого пробега" разносчиков от общего пройденного ими пути.

Пример входного файла
10 5 1 12
5 2 7 9 6 4 3 2 1 4 8 6

Пример выходного файла
36.7647