C. Искусство обращения с бакноматом
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Банкоматы одного известного банка одной небольшой страны устроены таким образом, что они могут выдать не любую сумму денег, запрошенную пользователем. Из-за ограниченного размера диспенсера купюр (устройства, непосредственно выдающего деньги в банкомате) и особенностей устройства банкомата, на руки можно получить не более, чем k купюр, при этом купюры могут быть не более, чем двух различных достоинств.

Например, если в стране используются купюры достоинствами 10, 50, 100, 500, 1000 и 5000 бурлей, то при k = 20 подобный банкомат может выдать суммы в 100 000 бурлей и в 96 000 бурлей, а вот суммы в 99 000 бурлей и 101 000 бурлей — уже не может.

Предположим, в стране находятся в хождении купюры n различных достоинств, при этом в банкомате, которым вы пользуетесь, находится неограниченное количество купюр каждого вида. Вы знаете, что в течение дня вам потребуется q раз снять некоторое количество наличных денег. Известно, что банкомат при наличии нескольких способов выдать сумму денег выбирает тот, в котором требуется минимальное количество банкнот, либо выдаёт сообщение об ошибке, если это сделать невозможно. Определите результат каждого из q запросов на выдачу наличных.

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

В первой строке находятся два целых числа n, k (1 ≤ n ≤ 5000, 1 ≤ k ≤ 20).

В следующей строке находятся n разделённых пробелами целых чисел ai (1 ≤ ai ≤ 107) — достоинства купюр, пребывающих в хождении в стране. Числа ai следуют в строго возрастающем порядке.

В следующей строке находится целое число q (1 ≤ q ≤ 20) — количество запросов на выдачу валюты, которые вы произведёте.

В последующих q строках находятся числа xi (1 ≤ xi ≤ 2·108) — суммы денег в бурлях, которые вы собираетесь получить в банкомате.

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

На каждый запрос выдачи валюты выведите в отдельной строке минимальное количество банкнот, которым может обойтись банкомат, либо выведите  - 1, если выдать соответствующую сумму невозможно.

Примеры
Входные данные
6 20
10 50 100 500 1000 5000
8
4200
100000
95000
96000
99000
10100
2015
9950
Выходные данные
6
20
19
20
-1
3
-1
-1
Входные данные
5 2
1 2 3 5 8
8
1
3
5
7
9
11
13
15
Выходные данные
1
1
1
2
2
2
2
-1