This is the hard version of the problem. The only difference is in the constraint on q. You can make hacks only if all versions of the problem are solved.

Zookeeper has been teaching his q sheep how to write and how to add. The i-th sheep has to write exactly k non-negative integers with the sum n_i.

Strangely, sheep have superstitions about digits and believe that the digits 3, 6, and 9 are lucky. To them, the fortune of a number depends on the decimal representation of the number; the fortune of a number is equal to the sum of fortunes of its digits, and the fortune of a digit depends on its value and position and can be described by the following table. For example, the number 319 has fortune F_{2} + 3F_{0}. 

<image>

Each sheep wants to maximize the sum of fortune among all its k written integers. Can you help them?

Input

The first line contains a single integer k (1 ≤ k ≤ 999999): the number of numbers each sheep has to write. 

The next line contains six integers F_0, F_1, F_2, F_3, F_4, F_5 (1 ≤ F_i ≤ 10^9): the fortune assigned to each digit. 

The next line contains a single integer q (1 ≤ q ≤ 100 000): the number of sheep.

Each of the next q lines contains a single integer n_i (1 ≤ n_i ≤ 999999): the sum of numbers that i-th sheep has to write.

Output

Print q lines, where the i-th line contains the maximum sum of fortune of all numbers of the i-th sheep.

Example

Input


3
1 2 3 4 5 6
2
57
63


Output


11
8

Note

In the first test case, 57 = 9 + 9 + 39. The three 9's contribute 1 ⋅ 3 and 3 at the tens position contributes 2 ⋅ 1. Hence the sum of fortune is 11.

In the second test case, 63 = 35 + 19 + 9. The sum of fortune is 8.
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.PrintStream;
import java.util.Arrays;
import java.io.IOException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) throws Exception {
        Thread thread = new Thread(null, new TaskAdapter(), "", 1 << 29);
        thread.start();
        thread.join();
    }

    static class TaskAdapter implements Runnable {
        @Override
        public void run() {
            InputStream inputStream = System.in;
            OutputStream outputStream = System.out;
            FastInput in = new FastInput(inputStream);
            PrintWriter out = new PrintWriter(outputStream);
            G2LuckyNumbersHardVersion solver = new G2LuckyNumbersHardVersion();
            solver.solve(1, in, out);
            out.close();
        }
    }

    static class G2LuckyNumbersHardVersion {
        Debug debug = new Debug(false);

        public void solve(int testNumber, FastInput in, PrintWriter out) {
            int k = in.readInt();
            long[] f = new long[6];
            in.populate(f);
            int limit = (int) 1e6;
            long[][] dp = new long[7][limit + 1];
            long inf = (long) 1e18;
            SequenceUtils.deepFill(dp, -inf);
            dp[0][0] = 0;
            LongMinQueue queue = new LongMinQueue(limit + 1, LongComparator.REVERSE_ORDER);

            for (int i = 1, base = 1; i <= 6; i++, base *= 10) {
                long profit = f[i - 1];
                int each = base * 3;
                int threshold = (k - 1) * 3 + 1;
                for (int j = 0; j < each; j++) {
                    queue.reset();
                    for (int t = j, x = 0; t <= limit; t += each, x++) {
                        queue.addLast(dp[i - 1][t] - x * profit);
                        if (threshold < queue.size()) {
                            queue.removeFirst();
                        }
                        dp[i][t] = queue.min() + x * profit;
                    }
                }

                for (int j = limit; j >= 0; j--) {
                    for (int t = 0; t <= 9; t++) {
                        if (j - t * base < 0) {
                            continue;
                        }
                        long cand = dp[i][j - t * base];
                        if (t % 3 == 0) {
                            cand += t / 3 * profit;
                        }
                        dp[i][j] = Math.max(dp[i][j], cand);
                    }
                }
            }

            debug.debug("dp", dp);
            int q = in.readInt();
            for (int i = 0; i < q; i++) {
                int n = in.readInt();
                long ans = dp[6][n];
                out.println(ans);
            }
        }

    }

    static class Debug {
        private boolean offline;
        private PrintStream out = System.err;
        static int[] empty = new int[0];

        public Debug(boolean enable) {
            offline = enable && System.getSecurityManager() == null;
        }

        public Debug debug(String name, Object x) {
            return debug(name, x, empty);
        }

        public Debug debug(String name, Object x, int... indexes) {
            if (offline) {
                if (x == null || !x.getClass().isArray()) {
                    out.append(name);
                    for (int i : indexes) {
                        out.printf("[%d]", i);
                    }
                    out.append("=").append("" + x);
                    out.println();
                } else {
                    indexes = Arrays.copyOf(indexes, indexes.length + 1);
                    if (x instanceof byte[]) {
                        byte[] arr = (byte[]) x;
                        for (int i = 0; i < arr.length; i++) {
                            indexes[indexes.length - 1] = i;
                            debug(name, arr[i], indexes);
                        }
                    } else if (x instanceof short[]) {
                        short[] arr = (short[]) x;
                        for (int i = 0; i < arr.length; i++) {
                            indexes[indexes.length - 1] = i;
                            debug(name, arr[i], indexes);
                        }
                    } else if (x instanceof boolean[]) {
                        boolean[] arr = (boolean[]) x;
                        for (int i = 0; i < arr.length; i++) {
                            indexes[indexes.length - 1] = i;
                            debug(name, arr[i], indexes);
                        }
                    } else if (x instanceof char[]) {
                        char[] arr = (char[]) x;
                        for (int i = 0; i < arr.length; i++) {
                            indexes[indexes.length - 1] = i;
                            debug(name, arr[i], indexes);
                        }
                    } else if (x instanceof int[]) {
                        int[] arr = (int[]) x;
                        for (int i = 0; i < arr.length; i++) {
                            indexes[indexes.length - 1] = i;
                            debug(name, arr[i], indexes);
                        }
                    } else if (x instanceof float[]) {
                        float[] arr = (float[]) x;
                        for (int i = 0; i < arr.length; i++) {
                            indexes[indexes.length - 1] = i;
                            debug(name, arr[i], indexes);
                        }
                    } else if (x instanceof double[]) {
                        double[] arr = (double[]) x;
                        for (int i = 0; i < arr.length; i++) {
                            indexes[indexes.length - 1] = i;
                            debug(name, arr[i], indexes);
                        }
                    } else if (x instanceof long[]) {
                        long[] arr = (long[]) x;
                        for (int i = 0; i < arr.length; i++) {
                            indexes[indexes.length - 1] = i;
                            debug(name, arr[i], indexes);
                        }
                    } else {
                        Object[] arr = (Object[]) x;
                        for (int i = 0; i < arr.length; i++) {
                            indexes[indexes.length - 1] = i;
                            debug(name, arr[i], indexes);
                        }
                    }
                }
            }
            return this;
        }

    }

    static class LongDequeImpl implements LongDeque {
        private long[] data;
        private int bpos;
        private int epos;
        private static final long[] EMPTY = new long[0];
        private int n;

        public LongDequeImpl(int cap) {
            if (cap == 0) {
                data = EMPTY;
            } else {
                data = new long[cap];
            }
            bpos = 0;
            epos = 0;
            n = cap;
        }

        private void expandSpace(int len) {
            while (n < len) {
                n = Math.max(n + 10, n * 2);
            }
            long[] newData = new long[n];
            if (bpos <= epos) {
                if (bpos < epos) {
                    System.arraycopy(data, bpos, newData, 0, epos - bpos);
                }
            } else {
                System.arraycopy(data, bpos, newData, 0, data.length - bpos);
                System.arraycopy(data, 0, newData, data.length - bpos, epos);
            }
            epos = size();
            bpos = 0;
            data = newData;
        }

        public LongIterator iterator() {
            return new LongIterator() {
                int index = bpos;


                public boolean hasNext() {
                    return index != epos;
                }


                public long next() {
                    long ans = data[index];
                    index = LongDequeImpl.this.next(index);
                    return ans;
                }
            };
        }

        public long removeFirst() {
            long ans = data[bpos];
            bpos = next(bpos);
            return ans;
        }

        public long removeLast() {
            long ans = data[last(epos)];
            epos = last(epos);
            return ans;
        }

        public void addLast(long x) {
            ensureMore();
            data[epos] = x;
            epos = next(epos);
        }

        public long peekFirst() {
            return data[bpos];
        }

        public long peekLast() {
            return data[last(epos)];
        }

        public void clear() {
            bpos = epos = 0;
        }

        private int last(int x) {
            return (x == 0 ? n : x) - 1;
        }

        private int next(int x) {
            return x + 1 >= n ? 0 : x + 1;
        }

        private void ensureMore() {
            if (next(epos) == bpos) {
                expandSpace(n + 1);
            }
        }

        public int size() {
            int ans = epos - bpos;
            if (ans < 0) {
                ans += data.length;
            }
            return ans;
        }

        public boolean isEmpty() {
            return bpos == epos;
        }

        public String toString() {
            StringBuilder builder = new StringBuilder();
            for (LongIterator iterator = iterator(); iterator.hasNext(); ) {
                builder.append(iterator.next()).append(' ');
            }
            return builder.toString();
        }

    }

    static class FastInput {
        private final InputStream is;
        private byte[] buf = new byte[1 << 13];
        private int bufLen;
        private int bufOffset;
        private int next;

        public FastInput(InputStream is) {
            this.is = is;
        }

        public void populate(long[] data) {
            for (int i = 0; i < data.length; i++) {
                data[i] = readLong();
            }
        }

        private int read() {
            while (bufLen == bufOffset) {
                bufOffset = 0;
                try {
                    bufLen = is.read(buf);
                } catch (IOException e) {
                    bufLen = -1;
                }
                if (bufLen == -1) {
                    return -1;
                }
            }
            return buf[bufOffset++];
        }

        public void skipBlank() {
            while (next >= 0 && next <= 32) {
                next = read();
            }
        }

        public int readInt() {
            int sign = 1;

            skipBlank();
            if (next == '+' || next == '-') {
                sign = next == '+' ? 1 : -1;
                next = read();
            }

            int val = 0;
            if (sign == 1) {
                while (next >= '0' && next <= '9') {
                    val = val * 10 + next - '0';
                    next = read();
                }
            } else {
                while (next >= '0' && next <= '9') {
                    val = val * 10 - next + '0';
                    next = read();
                }
            }

            return val;
        }

        public long readLong() {
            int sign = 1;

            skipBlank();
            if (next == '+' || next == '-') {
                sign = next == '+' ? 1 : -1;
                next = read();
            }

            long val = 0;
            if (sign == 1) {
                while (next >= '0' && next <= '9') {
                    val = val * 10 + next - '0';
                    next = read();
                }
            } else {
                while (next >= '0' && next <= '9') {
                    val = val * 10 - next + '0';
                    next = read();
                }
            }

            return val;
        }

    }

    static class LongMinQueue {
        LongDequeImpl minQueue;
        LongDequeImpl data;
        LongComparator comparator;

        public LongMinQueue(int cap, LongComparator comparator) {
            minQueue = new LongDequeImpl(cap);
            data = new LongDequeImpl(cap);
            this.comparator = comparator;
        }

        public void reset() {
            minQueue.clear();
            data.clear();
        }

        public void addLast(long val) {
            data.addLast(val);
            while (!minQueue.isEmpty() && comparator.compare(minQueue.peekLast(), val) > 0) {
                minQueue.removeLast();
            }
            minQueue.addLast(val);
        }

        public long removeFirst() {
            long val = data.removeFirst();
            if (minQueue.peekFirst() == val) {
                minQueue.removeFirst();
            }
            return val;
        }

        public int size() {
            return data.size();
        }

        public long min() {
            return minQueue.peekFirst();
        }

    }

    static interface LongDeque extends LongStack {
    }

    static interface LongComparator {
        public static final LongComparator REVERSE_ORDER = (a, b) -> Long.compare(b, a);

        public int compare(long a, long b);

    }

    static class SequenceUtils {
        public static void deepFill(Object array, long val) {
            if (!array.getClass().isArray()) {
                throw new IllegalArgumentException();
            }
            if (array instanceof long[]) {
                long[] longArray = (long[]) array;
                Arrays.fill(longArray, val);
            } else {
                Object[] objArray = (Object[]) array;
                for (Object obj : objArray) {
                    deepFill(obj, val);
                }
            }
        }

    }

    static interface LongStack {
    }

    static interface LongIterator {
        boolean hasNext();

        long next();

    }
}

