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.

Input

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

The next line contains n space-separated integers ai (1 ≤ ai ≤ 107) — the denominations of the bills that are used in the country. Numbers ai 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 xi (1 ≤ xi ≤ 2·108) — the sums of money in burles that you are going to withdraw from the ATM.

Output

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.

Examples

Input

6 20
10 50 100 500 1000 5000
8
4200
100000
95000
96000
99000
10100
2015
9950


Output

6
20
19
20
-1
3
-1
-1


Input

5 2
1 2 3 5 8
8
1
3
5
7
9
11
13
15


Output

1
1
1
2
2
2
2
-1
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5005;
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
using namespace std;
namespace fastIO {
bool IOerror = 0;
inline char nc() {
  static char buf[100005], *p1 = buf + 100005, *pend = buf + 100005;
  if (p1 == pend) {
    p1 = buf;
    pend = buf + fread(buf, 1, 100005, stdin);
    if (pend == p1) {
      IOerror = 1;
      return -1;
    }
  }
  return *p1++;
}
inline bool blank(char ch) {
  return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';
}
inline void read(int &x) {
  bool sign = 0;
  char ch = nc();
  x = 0;
  for (; blank(ch); ch = nc())
    ;
  if (IOerror) return;
  if (ch == '-') sign = 1, ch = nc();
  for (; ch >= '0' && ch <= '9'; ch = nc()) x = x * 10 + ch - '0';
  if (sign) x = -x;
}
inline void read(long long &x) {
  bool sign = 0;
  char ch = nc();
  x = 0;
  for (; blank(ch); ch = nc())
    ;
  if (IOerror) return;
  if (ch == '-') sign = 1, ch = nc();
  for (; ch >= '0' && ch <= '9'; ch = nc()) x = x * 10 + ch - '0';
  if (sign) x = -x;
}
inline void read(double &x) {
  bool sign = 0;
  char ch = nc();
  x = 0;
  for (; blank(ch); ch = nc())
    ;
  if (IOerror) return;
  if (ch == '-') sign = 1, ch = nc();
  for (; ch >= '0' && ch <= '9'; ch = nc()) x = x * 10 + ch - '0';
  if (ch == '.') {
    double tmp = 1;
    ch = nc();
    for (; ch >= '0' && ch <= '9'; ch = nc())
      tmp /= 10.0, x += tmp * (ch - '0');
  }
  if (sign) x = -x;
}
inline void read(char *s) {
  char ch = nc();
  for (; blank(ch); ch = nc())
    ;
  if (IOerror) return;
  for (; !blank(ch) && !IOerror; ch = nc()) *s++ = ch;
  *s = 0;
}
inline void read(char &c) {
  for (c = nc(); blank(c); c = nc())
    ;
  if (IOerror) {
    c = -1;
    return;
  }
}
inline void read1(int &x) {
  char ch;
  int bo = 0;
  x = 0;
  for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar())
    if (ch == '-') bo = 1;
  for (; ch >= '0' && ch <= '9'; x = x * 10 + ch - '0', ch = getchar())
    ;
  if (bo) x = -x;
}
inline void read1(long long &x) {
  char ch;
  int bo = 0;
  x = 0;
  for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar())
    if (ch == '-') bo = 1;
  for (; ch >= '0' && ch <= '9'; x = x * 10 + ch - '0', ch = getchar())
    ;
  if (bo) x = -x;
}
inline void read1(double &x) {
  char ch;
  int bo = 0;
  x = 0;
  for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar())
    if (ch == '-') bo = 1;
  for (; ch >= '0' && ch <= '9'; x = x * 10 + ch - '0', ch = getchar())
    ;
  if (ch == '.') {
    double tmp = 1;
    for (ch = getchar(); ch >= '0' && ch <= '9';
         tmp /= 10.0, x += tmp * (ch - '0'), ch = getchar())
      ;
  }
  if (bo) x = -x;
}
inline void read1(char *s) {
  char ch = getchar();
  for (; blank(ch); ch = getchar())
    ;
  for (; !blank(ch); ch = getchar()) *s++ = ch;
  *s = 0;
}
inline void read1(char &c) {
  for (c = getchar(); blank(c); c = getchar())
    ;
}
inline void read2(int &x) { scanf("%d", &x); }
inline void read2(long long &x) { scanf("%lld", &x); }
struct Ostream_fwrite {
  char *buf, *p1, *pend;
  Ostream_fwrite() {
    buf = new char[100005];
    p1 = buf;
    pend = buf + 100005;
  }
  void out(char ch) {
    if (p1 == pend) {
      fwrite(buf, 1, 100005, stdout);
      p1 = buf;
    }
    *p1++ = ch;
  }
  void print(int x) {
    static char s[15], *s1;
    s1 = s;
    if (!x) *s1++ = '0';
    if (x < 0) out('-'), x = -x;
    while (x) *s1++ = x % 10 + '0', x /= 10;
    while (s1-- != s) out(*s1);
  }
  void println(int x) {
    static char s[15], *s1;
    s1 = s;
    if (!x) *s1++ = '0';
    if (x < 0) out('-'), x = -x;
    while (x) *s1++ = x % 10 + '0', x /= 10;
    while (s1-- != s) out(*s1);
    out('\n');
  }
  void print(long long x) {
    static char s[25], *s1;
    s1 = s;
    if (!x) *s1++ = '0';
    if (x < 0) out('-'), x = -x;
    while (x) *s1++ = x % 10 + '0', x /= 10;
    while (s1-- != s) out(*s1);
  }
  void println(long long x) {
    static char s[25], *s1;
    s1 = s;
    if (!x) *s1++ = '0';
    if (x < 0) out('-'), x = -x;
    while (x) *s1++ = x % 10 + '0', x /= 10;
    while (s1-- != s) out(*s1);
    out('\n');
  }
  void print(double x, int y) {
    static long long mul[] = {1,
                              10,
                              100,
                              1000,
                              10000,
                              100000,
                              1000000,
                              10000000,
                              100000000,
                              1000000000,
                              10000000000LL,
                              100000000000LL,
                              1000000000000LL,
                              10000000000000LL,
                              100000000000000LL,
                              1000000000000000LL,
                              10000000000000000LL,
                              100000000000000000LL};
    if (x < -1e-12) out('-'), x = -x;
    x *= mul[y];
    long long x1 = (long long)floor(x);
    if (x - floor(x) >= 0.5) ++x1;
    long long x2 = x1 / mul[y], x3 = x1 - x2 * mul[y];
    print(x2);
    if (y > 0) {
      out('.');
      for (size_t i = 1; i < y && x3 * mul[i] < mul[y]; out('0'), ++i)
        ;
      print(x3);
    }
  }
  void println(double x, int y) {
    print(x, y);
    out('\n');
  }
  void print(char *s) {
    while (*s) out(*s++);
  }
  void println(char *s) {
    while (*s) out(*s++);
    out('\n');
  }
  void flush() {
    if (p1 != buf) {
      fwrite(buf, 1, p1 - buf, stdout);
      p1 = buf;
    }
  }
  ~Ostream_fwrite() { flush(); }
} Ostream;
inline void print(int x) { Ostream.print(x); }
inline void println(int x) { Ostream.println(x); }
inline void print(char x) { Ostream.out(x); }
inline void println(char x) {
  Ostream.out(x);
  Ostream.out('\n');
}
inline void print(long long x) { Ostream.print(x); }
inline void println(long long x) { Ostream.println(x); }
inline void print(double x, int y) { Ostream.print(x, y); }
inline void println(double x, int y) { Ostream.println(x, y); }
inline void print(char *s) { Ostream.print(s); }
inline void println(char *s) { Ostream.println(s); }
inline void println() { Ostream.out('\n'); }
inline void flush() { Ostream.flush(); }
char Out[100005], *o = Out;
inline void print1(int x) {
  static char buf[15];
  char *p1 = buf;
  if (!x) *p1++ = '0';
  if (x < 0) *o++ = '-', x = -x;
  while (x) *p1++ = x % 10 + '0', x /= 10;
  while (p1-- != buf) *o++ = *p1;
}
inline void println1(int x) {
  print1(x);
  *o++ = '\n';
}
inline void print1(long long x) {
  static char buf[25];
  char *p1 = buf;
  if (!x) *p1++ = '0';
  if (x < 0) *o++ = '-', x = -x;
  while (x) *p1++ = x % 10 + '0', x /= 10;
  while (p1-- != buf) *o++ = *p1;
}
inline void println1(long long x) {
  print1(x);
  *o++ = '\n';
}
inline void print1(char c) { *o++ = c; }
inline void println1(char c) {
  *o++ = c;
  *o++ = '\n';
}
inline void print1(char *s) {
  while (*s) *o++ = *s++;
}
inline void println1(char *s) {
  print1(s);
  *o++ = '\n';
}
inline void println1() { *o++ = '\n'; }
inline void flush1() {
  if (o != Out) {
    if (*(o - 1) == '\n') *--o = 0;
    puts(Out);
  }
}
struct puts_write {
  ~puts_write() { flush1(); }
} _puts;
inline void print2(int x) { printf("%d", x); }
inline void println2(int x) { printf("%d\n", x); }
inline void print2(char x) { printf("%c", x); }
inline void println2(char x) { printf("%c\n", x); }
inline void print2(long long x) { printf("%lld", x); }
inline void println2(long long x) {
  print2(x);
  printf("\n");
}
inline void println2() { printf("\n"); }
};  // namespace fastIO
using namespace fastIO;
int N, K;
int num[MAXN];
set<int> tofind;
int main() {
  read(N);
  read(K);
  for (int i = 1; i <= N; ++i) {
    read(num[i]);
    tofind.insert(num[i]);
  }
  int Q;
  read(Q);
  while (Q--) {
    int res = K + 1;
    int MMM;
    read(MMM);
    int temp;
    for (int i = 1; i <= N; ++i) {
      int limit = min(K, MMM / num[i]);
      for (int k = 0; k <= limit; ++k) {
        temp = MMM - num[i] * k;
        if (temp == 0) {
          res = min(res, k);
          continue;
        }
        for (int l = limit - k; l >= 1; --l)
          if (temp % l == 0 && tofind.find(temp / l) != tofind.end())
            res = min(res, k + l);
      }
    }
    if (res == K + 1)
      printf("-1\n");
    else
      printf("%d\n", res);
  }
  return 0;
}
