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.
#include <bits/stdc++.h>
namespace mem {
namespace stdval {
using i32 = int;
using i64 = long long int;
using u32 = unsigned int;
using u64 = unsigned long long int;
using f32 = float;
using f64 = double;
using f96 = long double;
using i128 = __int128_t;
using u128 = __uint128_t;
}  // namespace stdval
namespace utils {
using std::accumulate;
using std::cerr;
using std::cin;
using std::cout;
using std::endl;
using std::function;
using std::get;
using std::lower_bound;
using std::make_pair;
using std::make_tuple;
using std::max_element;
using std::min_element;
using std::reverse;
using std::shuffle;
using std::sort;
using std::swap;
using std::tie;
using std::unique;
using std::upper_bound;
}  // namespace utils
namespace random {
const int LuckyNumber = 20040726;
std::mt19937 rng(LuckyNumber ^
                 std::chrono::steady_clock::now().time_since_epoch().count());
std::mt19937_64 rng64(
    LuckyNumber ^ std::chrono::steady_clock::now().time_since_epoch().count());
template <class T>
inline T rand(T l, T r) {
  return std::uniform_int_distribution<T>(l, r)(rng);
}
template <class T>
inline T rand64(T l, T r) {
  return std::uniform_int_distribution<T>(l, r)(rng);
}
}  // namespace random
namespace modint {
template <const int mod>
struct Z {
  int x;
  inline Z() { x = 0; }
  inline Z(int t) { x = t; }
  inline void operator-=(Z a) { (x -= a.x) < 0 && (x += mod); }
  inline void operator+=(Z a) { (x += a.x) >= mod && (x -= mod); }
  inline void operator*=(Z a) { x = (long long)x * a.x % mod; }
  friend inline Z operator*(Z a, Z b) { return (long long)a.x * b.x % mod; }
  friend inline Z operator-(Z a, Z b) {
    return ((a.x -= b.x) < 0 && (a.x += mod)), a;
  }
  friend inline Z operator+(Z a, Z b) {
    return ((a.x += b.x) >= mod && (a.x -= mod)), a;
  }
};
template <const int mod>
inline Z<mod> finv(Z<mod> x) {
  if (x.x < 2) return x;
  return (mod - mod / x.x) * finv(mod % x.x);
}
template <const int mod>
inline Z<mod> fpow(Z<mod> a, int b) {
  Z<mod> s = 1;
  for (; b; b >>= 1, a = a * a)
    if (b & 1) s = s * a;
  return s;
}
template <const int mod>
inline void init_inverse(int n, Z<mod> *inv) {
  inv[0] = inv[1] = 1;
  for (int i = 2; i < n; i++) inv[i] = (mod - mod / i) * inv[mod % i];
}
template <const int mod>
inline void init_factorial(int n, Z<mod> *fac, Z<mod> *ifac) {
  fac[0] = 1, init_inverse(n, ifac);
  for (int i = 1; i < n; i++)
    fac[i] = fac[i - 1] * i, ifac[i] = ifac[i - 1] * ifac[i];
}
}  // namespace modint
namespace io {
template <const int mod>
inline void read(modint::Z<mod> &x) {
  read(x.x);
}
template <const int mod>
inline void print(modint::Z<mod> x) {
  print(x.x);
}
}  // namespace io
namespace math {
using std::max;
using std::min;
template <class T>
inline T abs(T x) {
  return x < 0 ? -x : x;
}
template <class T>
inline T gcd(T n, T m) {
  return m ? gcd(m, n % m) : n;
}
template <class T>
inline T lcm(T n, T m) {
  return n / gcd(n, m) * m;
}
template <const stdval::u64 p>
struct FastDiv {
  stdval::u64 t, i;
  inline FastDiv() : t(stdval::u64(-1) / p), i(mul_inv(p)) {}
  inline bool divide(stdval::u64 n) { return n * i <= t; }
  inline bool divide(stdval::i64 n) {
    return stdval::u64(n < 0 ? -n : n) * i <= t;
  }
  inline stdval::u64 mul_inv(stdval::u64 n) {
    stdval::u64 x = n;
    for (int i = 0; i < 5; ++i) x *= 2 - n * x;
    return x;
  }
};
template <const stdval::u64 b>
struct FastMod {
  stdval::u64 m;
  inline FastMod() : m(stdval::u64((stdval::u128(1) << 64) / b)) {}
  inline stdval::u64 reduce(stdval::u64 a) {
    stdval::u64 q = (stdval::u64)((stdval::u128(m) * a) >> 64);
    stdval::u64 r = a - q * b;
    return r >= b ? r - b : r;
  }
};
}  // namespace math
namespace container {
using std::get;
using std::make_pair;
using std::make_tuple;
using std::map;
using std::pair;
using std::priority_queue;
using std::queue;
using std::set;
using std::stack;
using std::tie;
using std::tuple;
using std::unordered_map;
using std::unordered_set;
template <class T>
struct vector : std::vector<T> {
  using std::vector<T>::vector;
  vector() : std::vector<T>() {}
  vector(const std::vector<T> &plain) : std::vector<T>(plain) {}
  inline void sort() { std::sort(this->begin(), this->end()); }
  inline void concat(const vector &rhs) {
    this->insert(this->end(), rhs.begin(), rhs.end());
  }
  inline bool includes(const T &x) const {
    return std::find(this->begin(), this->end(), x) != this->end();
  }
  template <class Function>
  inline void forEach(Function func) {
    for (const auto &it : *this) func(it);
  }
  inline vector slice(int l, int r) const {
    if (l > r) return {};
    if (r < this->size()) return vector(this->begin() + l, this->begin() + r);
    vector<int> rsp = (this->begin() + l, this->end());
    return rsp.resize(r - l), rsp;
  }
  inline void from(const std::set<T> &src) {
    this->resize(src.size());
    auto it = this->begin();
    for (const T e : src) *it++ = e;
  }
  template <class R, class Function>
  inline vector<R> _map(Function func) const {
    vector<R> res(this->size());
    for (size_t i = 0; i < this->size(); i++)
      res[i] = func(this->operator[](i));
    return res;
  }
  template <class R>
  inline vector<R> map(R func(T)) const {
    return this->_map<R>(func);
  }
  template <class R>
  inline vector<R> map(const std::function<R(T)> &func) const {
    return this->_map<R>(func);
  }
};
struct string : std::string {
  using std::string::string;
  string() : std::string("") {}
  string(const std::string &plain) : std::string(plain) {}
  template <class T>
  inline string join(const vector<T> &vet) const;
  vector<string> split(const string &dim) const {
    if (this->empty()) return {};
    char *src = new char[this->length() + 1];
    strcpy(src, this->c_str());
    char *tar = new char[dim.length() + 1];
    strcpy(tar, dim.c_str());
    vector<string> rsp;
    for (char *pos = strtok(src, tar); pos; pos = strtok(nullptr, tar))
      rsp.push_back(string(pos));
    delete[] src;
    delete[] tar;
    return rsp;
  }
  template <class... Args>
  static inline string format(const char *fm, Args... args) {
    int len = snprintf(nullptr, 0, fm, args...);
    char *buf = new char[len + 1];
    snprintf(buf, len + 1, fm, args...);
    string str(buf);
    delete[] buf;
    return str;
  }
  template <class... Args>
  static inline string format(const string &fm, Args... args) {
    return format(fm.c_str(), args...);
  }
};
inline string to_string(const float &x) { return std::to_string(x); }
inline string to_string(const double &x) { return std::to_string(x); }
inline string to_string(const long double &x) { return std::to_string(x); }
inline string to_string(const int &x) { return std::to_string(x); }
inline string to_string(const unsigned int &x) { return std::to_string(x); }
inline string to_string(const long long int &x) { return std::to_string(x); }
inline string to_string(const unsigned long long int &x) {
  return std::to_string(x);
}
inline string to_string(const string &s) { return s; }
inline string to_string(const char *s) { return string(s); }
inline string to_string(const std::string &s) { return string(s); }
template <const int mod>
inline string to_string(const mem::modint::Z<mod> &v) {
  return std::to_string(v.x);
}
template <class T>
inline string to_string(const vector<T> &ctn) {
  return "[" + string(",").join(ctn) + "]";
}
template <class T>
inline string to_string(const set<T> &ctn) {
  string result = "{";
  bool flag = false;
  for (const auto &it : ctn) {
    if (flag) result += ",";
    flag = true;
    result += to_string(it);
  }
  return result + "}";
}
template <class T1, class T2>
inline string to_string(const map<T1, T2> &ctn) {
  string result = "{";
  bool flag = false;
  for (const auto &it : ctn) {
    if (flag) result += ",";
    flag = true;
    result += to_string(it.first) + ":" + to_string(it.second);
  }
  return result + "}";
}
template <class T>
inline string string::join(const vector<T> &vet) const {
  if (!vet.size()) return "";
  string res = to_string(vet[0]);
  for (size_t i = 1; i < vet.size(); i++) {
    res += *this;
    res += to_string(vet[i]);
  }
  return res;
}
inline string operator"" _s(const char *s) { return string(s); }
inline string operator"" _s(const char *s, size_t len) {
  return string(s, len);
}
inline string operator"" _s(long double x) { return to_string(x); }
inline string operator"" _s(unsigned long long int x) { return to_string(x); }
}  // namespace container
namespace io {
namespace fastio {
const int BUFFER = 1 << 18;
char ibuf[BUFFER], *iS, *iT;
inline int getc() {
  if (iS == iT) {
    iT = (iS = ibuf) + fread(ibuf, 1, BUFFER, stdin);
    return iS == iT ? EOF : *iS++;
  } else {
    return *iS++;
  }
}
char obuf[BUFFER], *oS = obuf, *oT = oS + BUFFER - 1;
inline void flush() {
  fwrite(obuf, 1, oS - obuf, stdout);
  oS = obuf;
}
inline void putc(int x) {
  *oS++ = x;
  if (oS == oT) flush();
}
struct Flusher {
  ~Flusher() { flush(); }
} flusher;
}  // namespace fastio
using fastio::getc;
using fastio::putc;
template <class T>
inline void readDigit(T &x) {
  x = getc();
  while (!isdigit(x)) x = getc();
}
inline int readDigit() {
  int x;
  readDigit(x);
  return x;
}
template <class T>
inline void readAlpha(T &x) {
  x = getc();
  while (!isalpha(x)) x = getc();
}
inline int readAlpha() {
  int x;
  readAlpha(x);
  return x;
}
inline void read(int &x) {
  x = 0;
  bool f = 0;
  char c = getc();
  while (!isdigit(c)) f ^= c == '-', c = getc();
  while (isdigit(c)) x = x * 10 + c - '0', c = getc();
  if (f) x = -x;
}
inline void read(unsigned int &x) {
  x = 0;
  bool f = 0;
  char c = getc();
  while (!isdigit(c)) f ^= c == '-', c = getc();
  while (isdigit(c)) x = x * 10 + c - '0', c = getc();
  if (f) x = -x;
}
inline void read(long long int &x) {
  x = 0;
  bool f = 0;
  char c = getc();
  while (!isdigit(c)) f ^= c == '-', c = getc();
  while (isdigit(c)) x = x * 10 + c - '0', c = getc();
  if (f) x = -x;
}
inline void read(unsigned long long int &x) {
  x = 0;
  bool f = 0;
  char c = getc();
  while (!isdigit(c)) f ^= c == '-', c = getc();
  while (isdigit(c)) x = x * 10 + c - '0', c = getc();
  if (f) x = -x;
}
inline void read(char &x) { x = getc(); }
inline void read(char *s) {
  char c = getc();
  while (~c && !isspace(c)) *s++ = c, c = getc();
  *s++ = '\0';
}
inline void read(container::string &s) {
  char c = getc();
  s = "";
  while (~c && !isspace(c)) s += c, c = getc();
}
template <class T = int>
inline T read() {
  T x;
  read(x);
  return x;
}
template <class T, class... Args>
inline void read(T &x, Args &...args) {
  read(x), read(args...);
}
inline void print(int x) {
  if (x < 0) putc('-'), x = -x;
  if (x > 9) print(x / 10);
  putc('0' + x % 10);
}
inline void print(unsigned int x) {
  if (x < 0) putc('-'), x = -x;
  if (x > 9) print(x / 10);
  putc('0' + x % 10);
}
inline void print(long long int x) {
  if (x < 0) putc('-'), x = -x;
  if (x > 9) print(x / 10);
  putc('0' + x % 10);
}
inline void print(unsigned long long int x) {
  if (x < 0) putc('-'), x = -x;
  if (x > 9) print(x / 10);
  putc('0' + x % 10);
}
inline void print(char x) { putc(x); }
inline void print(const char *s) {
  int len = strlen(s);
  for (int i = 0; i < len; i++) putc(s[i]);
}
inline void print(const container::string &s) {
  for (int i = 0; i < s.length(); i++) putc(s[i]);
}
template <class T, class... Args>
inline void print(const T &x, Args... args) {
  print(x), print(args...);
}
template <class... Args>
inline void println(Args... args) {
  print(args...), putc('\n');
}
template <class... Args>
inline void printfm(const char *formatter, Args... arguments) {
  print(container::string().format(formatter, arguments...));
}
template <class... Args>
inline void printfm(const container::string &formatter, Args... arguments) {
  print(container::string().format(formatter, arguments...));
}
}  // namespace io
namespace logger {
enum ConsoleColor {
  NOPE = -1,
  BLACK,
  RED,
  GREEN,
  YELLOW,
  BLUE,
  PURPLE,
  DEEPBLUE
};
template <const ConsoleColor color = NOPE, class... Args>
inline void log(const char *formatter, Args... args) {
  if (~color) {
    fprintf(stderr, "\033[%dm", 30 + color);
    fprintf(stderr, formatter, args...);
    fprintf(stderr, "\033[0m");
  } else {
    fprintf(stderr, formatter, args...);
  }
}
template <const ConsoleColor color = NOPE, class... Args>
inline void logln(const char *formatter, Args... args) {
  if (~color) {
    fprintf(stderr, "\033[%dm", 30 + color);
    fprintf(stderr, formatter, args...);
    fprintf(stderr, "\033[0m\n");
  } else {
    fprintf(stderr, formatter, args...);
    fprintf(stderr, "\n");
  }
}
template <class T>
inline void logs(const T &x) {
  fprintf(stderr, container::to_string(x).c_str());
}
template <class T, class... Args>
inline void logs(const T &x, Args... args) {
  logs(x), logs(args...);
}
template <class... Args>
inline void logsln(Args... args) {
  logs(args...);
  fprintf(stderr, "\n");
}
}  // namespace logger
using namespace io;
using namespace math;
using namespace utils;
using namespace modint;
using namespace random;
using namespace stdval;
using namespace logger;
using namespace container;
}  // namespace mem
using namespace mem;
const int N = 1e6 + 10;
const long long inf = 1e18;
int k, q, f[6], stk[N << 1];
long long dp[6][N];
inline int weight(int k) { return k % 3 == 0 ? k / 3 : 0; }
inline long long calc(int s) {
  if ((s + 8) / 9 > k) {
    return -inf;
  }
  int t = s / 9;
  s -= t * 9;
  if (t + 2 > k) {
    return t * 3 + weight(s);
  } else {
    return t * 3 + s / 3;
  }
}
inline vector<long long> transform(vector<long long> dp, int val) {
  vector<vector<long long>> g(3, vector<long long>(dp.size(), -inf));
  for (int r = 0; r < 9; r++)
    for (int cas = 0; cas < 3; cas++) {
      int u = 1, v = 0;
      for (int j = r, l = 0; j < dp.size(); j += 9, l++) {
        while (u <= v &&
               dp[j] - 3ll * l * val > dp[stk[v] * 9 + r] - 3ll * stk[v] * val)
          --v;
        stk[++v] = l;
        while (u <= v && k - cas < l - stk[u]) ++u;
        if (u <= v) {
          g[cas][j] = 3ll * l * val + dp[stk[u] * 9 + r] - 3ll * val * stk[u];
        }
      }
    }
  for (int i = 0; i < dp.size(); i++) {
    dp[i] = max(dp[i], g[0][i]);
    for (int j = i; j >= max<int>(0, i - 9); j--) {
      dp[i] = max(dp[i], g[1][j] + (long long)weight(i - j) * val);
    }
    for (int j = i; j >= max<int>(0, i - 9); j--) {
      dp[i] = max(dp[i], g[2][j] + (long long)(i - j) / 3 * val);
    }
  }
  return dp;
}
int32_t main() {
  read(k);
  for (int i = 0; i < 6; i++) {
    read(f[i]);
  }
  for (int i = 0; i < 1000000; i++) {
    long long t = calc(i);
    if (t < 0) {
      dp[0][i] = -inf;
    } else {
      dp[0][i] = (long long)t * f[0];
    }
  }
  int w = 10;
  for (int k = 1; k < 6; k++, w *= 10) {
    for (int r = 0; r < w; r++) {
      vector<long long> src;
      for (int i = r; i < 1000000; i += w) {
        src.push_back(dp[k - 1][i]);
      }
      vector<long long> rsp = transform(src, f[k]);
      for (int i = r, j = 0; i < 1000000; i += w, j++) {
        dp[k][i] = rsp[j];
      }
    }
  }
  read(q);
  while (q-- > 0) {
    int x;
    read(x);
    print(dp[5][x], '\n');
  }
}
