CF524C.The Art of Dealing with ATM

ATMs of a well-known bank of a small country are arranged so that they can not give any amount of money requested by the user. Due to the limited size of the bill dispenser (the device that is directly giving money from an ATM) and some peculiarities of the ATM structure, you can get at most k bills from it, and the bills may be of at most two distinct denominations.

For example, if a country uses bills with denominations 10, 50, 100, 500, 1000 and 5000 burles, then at k = 20 such ATM can give sums 100 000 burles and 96 000 burles, but it cannot give sums 99 000 and 101 000 burles.

Let's suppose that the country uses bills of n distinct denominations, and the ATM that you are using has an unlimited number of bills of each type. You know that during the day you will need to withdraw a certain amount of cash q times. You know that when the ATM has multiple ways to give money, it chooses the one which requires the minimum number of bills, or displays an error message if it cannot be done. Determine the result of each of the q of requests for cash withdrawal.

一家知名银行在某小国的自动取款机（ATM）具有特殊限制：无法向用户支付任意请求的金额。由于钞票出钞装置（即 ATM 中直接向用户发放现金的部件）容量有限，以及 ATM 结构本身的某些特殊性，每次最多只能给出 $k$ 张钞票，且这些钞票的面额至多只能有两种不同的面值。

例如，若该国使用的钞票面额为 $10$、$50$、$100$、$500$、$1000$ 和 $5000$ 伯尔（burles），则当 $k = 20$ 时，此类 ATM 可以支付 $100\,000$ 伯尔和 $96\,000$ 伯尔，但无法支付 $99\,000$ 伯尔和 $101\,000$ 伯尔。

假设该国共使用 $n$ 种不同面额的钞票，而您正在使用的 ATM 每种面额的钞票数量均无限。已知您当天需进行 $q$ 次现金提取操作。还已知：当 ATM 存在多种支付方式时，它将选择所需钞票张数最少的那种方式；若无法支付，则显示错误信息。请确定这 $q$ 次取款请求各自的结果。

The first line contains two integers n, k (1 ≤ n ≤ 5000, 1 ≤ k ≤ 20).

The next line contains n space-separated integers a__i (1 ≤ a__i ≤ 107) — the denominations of the bills that are used in the country. Numbers a__i follow in the strictly increasing order.

The next line contains integer q (1 ≤ q ≤ 20) — the number of requests for cash withdrawal that you will make.

The next q lines contain numbers x__i (1 ≤ x__i ≤ 2·108) — the sums of money in burles that you are going to withdraw from the ATM.

第一行包含两个整数 $n$、$k$（$1 \leq n \leq 5000$，$1 \leq k \leq 20$）。

第二行包含 $n$ 个用空格分隔的整数 $a_i$（$1 \leq a_i \leq 10^7$）——表示该国流通纸币的面额。这些数 $a_i$ 严格递增排列。

第三行包含一个整数 $q$（$1 \leq q \leq 20$）——表示你将进行的取款请求次数。

接下来的 $q$ 行每行包含一个数 $x_i$（$1 \leq x_i \leq 2 \cdot 10^8$）——表示你计划从 ATM 中提取的金额（单位：burles）。

For each request for cash withdrawal print on a single line the minimum number of bills it can be done, or print  - 1, if it is impossible to get the corresponding sum.

对于每笔取款请求，请在一行中输出完成该取款所需的最少纸币张数；若无法凑出对应金额，则输出 -1。