B"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} . Each sheep wants to maximize the sum of fortune among all its k written integers. Can you help them? The first line contains a single integer k ( 1 <= q k <= q 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 <= q F_i <= q 10^9 ): the fortune assigned to each digit. The next line contains a single integer q ( 1 <= q q <= q 100 ,000 ): the number of sheep. Each of the next q lines contains a single integer n_i ( 1 <= q n_i <= q 999999 ): the sum of numbers that i -th sheep has to write. Print q lines, where the i -th line contains the maximum sum of fortune of all numbers of the i -th sheep. In the first test case, 57 = 9 + 9 + 39 . The three 9 's contribute 1 cdot 3 and 3 at the tens position contributes 2 cdot 1 . Hence the sum of fortune is 11 . In the second test case, 63 = 35 + 19 + 9 . The sum of fortune is 8 . "...