Задача . Охлаждение реактора

Охлаждение реактора

В энергетическом реакторе находятся N нагретых элементов. Температура элемента i равна a_i условных единиц.

Система охлаждения позволяет установить общий верхний предел температуры T (целое число от 0 до M включительно). После включения системы каждый элемент с начальной температурой выше T охлаждается ровно до T. Температуры остальных элементов не меняются.

При уменьшении температуры одного элемента на одну единицу из реактора извлекается одна единица энергии.

Инженеры подготовили Q независимых заявок. В каждой заявке известно количество энергии B, которое необходимо извлечь.

Для каждой заявки определите максимально возможный целый предел температуры T, при котором извлекается не менее B единиц энергии. Если это невозможно даже при T = 0, выведите -1.

Входные данные

Первая строка содержит N, M и Q (1 ≤ N ≤ 200000, 1 ≤ M ≤ 200000, 1 ≤ Q ≤ 200000).

Вторая строка содержит N целых чисел a_i (0 ≤ a_i ≤ M).

Следующие Q строк содержат по одному целому числу B (0 ≤ B ≤ 10¹²).

Выходные данные

Для каждой заявки выведите найденное T либо -1, по одному числу на строку.

4 8 5
5 2 8 5
0
3
7
20
21

8
5
3
0
-1