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
import java.io.*;
import java.util.*;

/**
* @author master_j
* @version 0.4.1
* @since Mar 22, 2015
*/
public class Solution {
    private void solve() throws IOException {
        int n = io.nI(), k = io.nI();
        int[] a = io.nIa(n);
        Map<Integer, Integer> sumToNum = new HashMap<>();
        sumToNum.put(0, 0);
        for (int i = 0; i < n; i++) {
            int b = a[i];
            for (int j = 1; j <= k; j++)
                sumToNum.put(b*j, j);
        }
        int Z = io.nI();
        for (int z = 0; z < Z; z++) {
            int x = io.nI(), ans = 1 + k;
            for (int b : a)
                for (int j = 0; j <= k; j++) {
                    Integer t = sumToNum.get(x - b*j);
                    if(t != null)
                        ans = Math.min(ans, j + t);
                }
            io.wln(ans <= k ? ans : -1);
        }
    }//2.2250738585072012e-308

    public static void main(String[] args) throws IOException {
        IO.launchSolution(args);
    }

    Solution(IO io) throws IOException {
        this.io = io;
        solve();
    }

    private final IO io;
}

class IO {
    static final String _localArg = "master_j";
    private static final String _problemName = "";
    private static final IO.Mode _inMode = Mode.STD_;
    private static final IO.Mode _outMode = Mode.STD_;
    private static final boolean _autoFlush = false;

    static enum Mode {STD_, _PUT_TXT, PROBNAME_}

    private final StreamTokenizer st;
    private final BufferedReader br;
    private final Reader reader;

    private final PrintWriter pw;
    private final Writer writer;

    static void launchSolution(String[] args) throws IOException {
        boolean local = (args.length == 1 && args[0].equals(IO._localArg));
        IO io = new IO(local);

        long nanoTime = 0;
        if (local) {
            nanoTime -= System.nanoTime();
            io.wln("<output>");
        }

        io.flush();
        new Solution(io);
        io.flush();

        if (local) {
            io.wln("</output>");
            nanoTime += System.nanoTime();
            final long D9 = 1000000000, D6 = 1000000, D3 = 1000;
            if (nanoTime >= D9)
                io.wf("%d.%d seconds\n", nanoTime / D9, nanoTime % D9);
            else if (nanoTime >= D6)
                io.wf("%d.%d millis\n", nanoTime / D6, nanoTime % D6);
            else if (nanoTime >= D3)
                io.wf("%d.%d micros\n", nanoTime / D3, nanoTime % D3);
            else
                io.wf("%d nanos\n", nanoTime);
        }

        io.close();
    }

    IO(boolean local) throws IOException {
        if (_inMode == Mode.PROBNAME_ || _outMode == Mode.PROBNAME_)
            if (_problemName.length() == 0)
                throw new IllegalStateException("You imbecile. Where's my <_problemName>?");

        if (_problemName.length() > 0)
            if (_inMode != Mode.PROBNAME_ && _outMode != Mode.PROBNAME_)
                throw new IllegalStateException("You imbecile. What's the <_problemName> for?");

        Locale.setDefault(Locale.US);

        if (local) {
            reader = new FileReader("input.txt");
            writer = new OutputStreamWriter(System.out);
        } else {
            switch (_inMode) {
                case STD_:
                    reader = new InputStreamReader(System.in);
                    break;
                case PROBNAME_:
                    reader = new FileReader(_problemName + ".in");
                    break;
                case _PUT_TXT:
                    reader = new FileReader("input.txt");
                    break;
                default:
                    throw new NullPointerException("You imbecile. Gimme _inMode.");
            }
            switch (_outMode) {
                case STD_:
                    writer = new OutputStreamWriter(System.out);
                    break;
                case PROBNAME_:
                    writer = new FileWriter(_problemName + ".out");
                    break;
                case _PUT_TXT:
                    writer = new FileWriter("output.txt");
                    break;
                default:
                    throw new NullPointerException("You imbecile. Gimme _outMode.");
            }
        }

        br = new BufferedReader(reader);
        st = new StreamTokenizer(br);

        pw = new PrintWriter(writer, _autoFlush);

        if (local && _autoFlush)
            wln("Note: auto-flush is on.");
    }

    void wln()          {pw.println(); }
    void wln(boolean x) {pw.println(x);}
    void wln(char x)    {pw.println(x);}
    void wln(char x[])  {pw.println(x);}
    void wln(double x)  {pw.println(x);}
    void wln(float x)   {pw.println(x);}
    void wln(int x)     {pw.println(x);}
    void wln(long x)    {pw.println(x);}
    void wln(Object x)  {pw.println(x);}
    void wln(String x)  {pw.println(x);}

    void wf(String f, Object...o){pw.printf(f, o);}

    void w(boolean x)   {pw.print(x);}
    void w(char x)      {pw.print(x);}
    void w(char x[])    {pw.print(x);}
    void w(double x)    {pw.print(x);}
    void w(float x)     {pw.print(x);}
    void w(int x)       {pw.print(x);}
    void w(long x)      {pw.print(x);}
    void w(Object x)    {pw.print(x);}
    void w(String x)    {pw.print(x);}

    int nI() throws IOException    {st.nextToken(); return (int)st.nval;}
    double nD() throws IOException {st.nextToken(); return st.nval;}
    float nF() throws IOException  {st.nextToken(); return (float)st.nval;}
    long nL() throws IOException   {st.nextToken(); return (long)st.nval;}
    String nS() throws IOException {st.nextToken(); return st.sval;}

    int[] nIa(int n) throws IOException {
        int[] a = new int[n];
        for (int i = 0; i < n; i++)
            a[i] = nI();
        return a;
    }
    double[] nDa(int n) throws IOException {
        double[] a = new double[n];
        for (int i = 0; i < n; i++)
            a[i] = nD();
        return a;
    }
    String[] nSa(int n) throws IOException {
        String[] a = new String[n];
        for (int i = 0; i < n; i++)
            a[i] = nS();
        return a;
    }

    void wc(String x)         {wc(x.toCharArray());}
    void wc(char c1, char c2) {for (char c = c1; c<=c2; c++) wc(c);}
    void wc(char x[])         {for (char c : x) wc(c); }
    void wc(char x)           {st.ordinaryChar(x); st.wordChars(x, x);}

    public boolean eof() {return st.ttype == StreamTokenizer.TT_EOF;}
    public boolean eol() {return st.ttype == StreamTokenizer.TT_EOL;}

    void flush() {pw.flush();}
    void close() throws IOException {reader.close(); br.close(); flush(); pw.close();}
}