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

public class Main{
	static int maxn=1000000;
	static long inf=(long)1e16;
	static long fill=(long)-1e18;
	static ArrayList<Integer>weights;
	static ArrayList<Long>vals;
	static long[]memo;
	
	static int[]F;
	static long cost(int num) {
		int d=0;
		long ans=0;
		while(num>0) {
			int digit=num%10;
			num/=10;
			if(digit==3 || digit==6 || digit==9) {
				ans+=F[d]*1l*(digit/3);
			}
			d++;
		}
		return ans;
	}
	static void main() throws Exception{
		int n=(sc.nextInt()-1)*3;
		F=sc.intArr(6);
		vals=new ArrayList<Long>();
		weights=new ArrayList<Integer>();
		int ten=1;
		for(int i=0;i<6;i++) {
			int curW=3*ten;long curV=F[i];
			int cur=1;
			int tmpn=n;
			while(cur<=tmpn) {
				if(curW*1l*cur>maxn)break;
				weights.add(curW*cur);
				vals.add(curV*cur);
				tmpn-=cur;
				cur<<=1;
			}
			if(tmpn>0 && curW*1l*tmpn<=maxn) {
				weights.add(curW*tmpn);
				vals.add(curV*tmpn);
			}
			ten*=10;
		}
		memo=new long[maxn];
		for(int i=1;i<maxn;i++) {
			memo[i]=-inf;
		}
		
		for(int i=0;i<weights.size();i++) {
			long[]newMemo=new long[maxn];
			for(int sum=0;sum<maxn;sum++) {
				int nxtSum=sum-weights.get(i);
				newMemo[sum]=Math.max(memo[sum], vals.get(i)+(nxtSum<0?(-inf):(memo[nxtSum])));
			}
			memo=newMemo;
		}
		ten=1;
		for(int d=0;d<6;d++) {
			for(int sum=maxn-1;sum>=0;sum--) {
				for(int curD=1;curD<=9;curD++) {
					int nxtSum=sum-ten*curD;
					if(nxtSum<0)continue;
					long val=(curD%3!=0?0:(curD/3))*1l*F[d];
					memo[sum]=Math.max(memo[sum], memo[nxtSum]+val);
				}
			}
			ten*=10;
		}
		
		int q=sc.nextInt();
		while(q-->0)
			pw.println(memo[sc.nextInt()]);
		
	}
	public static void main(String[] args) throws Exception{
		sc=new MScanner(System.in);
		pw = new PrintWriter(System.out);
//		int tc=1;
//		tc=sc.nextInt();
//		while(tc-->0)
			main();
		pw.flush();
	}
	static PrintWriter pw;
	static MScanner sc;
	static class MScanner {
		StringTokenizer st;
		BufferedReader br;
		public MScanner(InputStream system) {
			br = new BufferedReader(new InputStreamReader(system));
		}
	 
		public MScanner(String file) throws Exception {
			br = new BufferedReader(new FileReader(file));
		}
	 
		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}
		public int[] intArr(int n) throws IOException {
	        int[]in=new int[n];for(int i=0;i<n;i++)in[i]=nextInt();
	        return in;
		}
		public long[] longArr(int n) throws IOException {
	        long[]in=new long[n];for(int i=0;i<n;i++)in[i]=nextLong();
	        return in;
		}
		public int[] intSortedArr(int n) throws IOException {
	        int[]in=new int[n];for(int i=0;i<n;i++)in[i]=nextInt();
	        shuffle(in);
	        Arrays.sort(in);
	        return in;
		}
		public long[] longSortedArr(int n) throws IOException {
	        long[]in=new long[n];for(int i=0;i<n;i++)in[i]=nextLong();
	        shuffle(in);
	        Arrays.sort(in);
	        return in;
		}
		public Integer[] IntegerArr(int n) throws IOException {
	        Integer[]in=new Integer[n];for(int i=0;i<n;i++)in[i]=nextInt();
	        return in;
		}
		public Long[] LongArr(int n) throws IOException {
	        Long[]in=new Long[n];for(int i=0;i<n;i++)in[i]=nextLong();
	        return in;
		}
		public String nextLine() throws IOException {
			return br.readLine();
		}
	 
		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}
	 
		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}
	 
		public char nextChar() throws IOException {
			return next().charAt(0);
		}
	 
		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}
	 
		public boolean ready() throws IOException {
			return br.ready();
		}
	 
		public void waitForInput() throws InterruptedException {
			Thread.sleep(3000);
		}
		
	}
	static void shuffle(int[]in) {
		for(int i=0;i<in.length;i++) {
			int idx=(int)(Math.random()*in.length);
			int tmp=in[i];
			in[i]=in[idx];
			in[idx]=tmp;
		}
	}
	static void shuffle(long[]in) {
		for(int i=0;i<in.length;i++) {
			int idx=(int)(Math.random()*in.length);
			long tmp=in[i];
			in[i]=in[idx];
			in[idx]=tmp;
		}
	}
}