Банкоматы одного известного банка одной небольшой страны устроены таким образом, что они могут выдать не любую сумму денег, запрошенную пользователем. Из-за ограниченного размера диспенсера купюр (устройства, непосредственно выдающего деньги в банкомате) и особенностей устройства банкомата, на руки можно получить не более, чем k купюр, при этом купюры могут быть не более, чем двух различных достоинств.
Например, если в стране используются купюры достоинствами 10, 50, 100, 500, 1000 и 5000 бурлей, то при k = 20 подобный банкомат может выдать суммы в 100 000 бурлей и в 96 000 бурлей, а вот суммы в 99 000 бурлей и 101 000 бурлей — уже не может.
Предположим, в стране находятся в хождении купюры n различных достоинств, при этом в банкомате, которым вы пользуетесь, находится неограниченное количество купюр каждого вида. Вы знаете, что в течение дня вам потребуется q раз снять некоторое количество наличных денег. Известно, что банкомат при наличии нескольких способов выдать сумму денег выбирает тот, в котором требуется минимальное количество банкнот, либо выдаёт сообщение об ошибке, если это сделать невозможно. Определите результат каждого из q запросов на выдачу наличных.
Выходные данные
На каждый запрос выдачи валюты выведите в отдельной строке минимальное количество банкнот, которым может обойтись банкомат, либо выведите - 1, если выдать соответствующую сумму невозможно.