22059번 - Аллея 다국어

Недавно Боре приснился сон, в котором он ходил по очень длинной аллее. Вдоль нее были посажены деревья, причём расстояние между любыми двумя деревьями измеряется целым числом метров. В самом начале, и в самом конце аллеи росло по дереву.

Поскольку Боря очень любит математику, он решил придумать формулу, с помощью которой он сможет оценить красоту аллеи некоторым числом. В голову ему пришла такая идея. Посчитаем максимальное расстояние между двумя соседними деревьями. Это число будем называть неравномерностью аллеи. И чем оно меньше, тем красивее аллея по мнению Бори.

Поскольку аллея была очень длинной, прогулка Бори затянулась, и ему стало интересно, насколько красивой могла бы стать аллея, если бы вдоль нее посадили еще k деревьев? Заметим, что чтобы не нарушать гармонию, расстояние между каждой парой деревьев, измеренное в метрах, должно быть целым числом. При этом разрешается сажать несколько деревьев в одну точку, в том числе в точки, где уже растут деревья. Помогите Боре найти наименьшее значение неравномерности аллеи для различных k.

Первая строка содержит три целых числа n, m и len (2 ≤ n, m ≤ 10⁶, 1 ≤ len ≤ 10⁹) — количество уже посаженных деревьев, количество значений k, которые интересуют Борю, а также длину аллеи. Вторая строка содержит n целых чисел a₁, ..., a_n (0 = a₁ < a₂ < ... < a_n = len) — расстояния от начала аллеи до i-го дерева, измеренное в метрах. Третья строка содержит m целых чисел k₁, ..., k_m (0 ≤ k_i ≤ 10⁹ для всех i от 1 до m) — вопросы Бори.

Выведите m вещественных чисел — минимальные значения неравномерности аллеи, если будет посажено еще k₁, ..., k_m деревьев. Выводите каждое из чисел в отдельной строке.