Five for week 16 (2013-2014)
Упаковка воды
Шло время, изина вода становилась всё известнее и популярнее, пока, наконец, Изя не стал основным поставщиком воды в стране. Все крупные корпорации, заведения, просто коллективы считали своим долгом покупать воду только у Изи. И, когда дело достигло таких масштабов, появились новые проблемы.
Заказы стали приходить на очень большое количество воды. Такое, что не уместится ни в одну бутылку. Поэтому Изя нанял фургон, на котором воду можно доставлять в любых количествах. Теперь оставался только один вопрос – как отмерить необходимый объём?
К счастью, у Изи оказалось целых N видов бутылок, каждая из которых была рассчитана на определённый объём воды. Теперь оказалось необходимо для каждого заказа наиболее компактно разлить соответствующее количество воды по бутылям.
Input data
В первой строке содержится одно число N (2 ≤ N ≤ 10) – количество видов бутылок, которые есть у Изи.
Во второй строке через пробел задано N натуральных чисел ai (1 ≤ ai ≤ 1000)– объём, помещающийся в i-ю бутылку. Следует отметить, что разные виды бутылок не обязательно различаются по объёму. Количество бутылок каждого вида неограниченно.
В третьей строке содержится одно число M (1 ≤ M ≤ 100000) – количество заказов, поступивших Изе.
В каждой из M следующих строк содержится одно число Xj (1 ≤ Xj ≤ 1014) – требуемый объём воды для j-го заказа.
Output data
Для каждого из M заказов в отдельной строке выведите минимальное число бутылок, в которые можно разлить ровно Xj воды. Если же не существует такого набора бутылок, выведите -1.
Examples
2 2 3 7 1 2 3 4 5 6 7
-1 1 1 2 2 2 3