CF1428G2 Lucky Numbers (Hard Version)

这是该问题的难度较高版本，唯一的区别在于 $q$ 的约束条件。只有在所有版本的问题都被解决后，你才能进行 hack。 动物园管理员正在教他的 $q$ 只羊如何写数字和做加法。第 $i$ 只羊需要写出恰好 $k$ 个非负整数，这些整数的和为 $n_i$。 奇怪的是，羊对数字有迷信，认为数字 $3$、$6$ 和 $9$ 是幸运数字。对它们来说，一个数的“幸运值”取决于它的十进制表示；一个数的幸运值等于其各位数字幸运值之和，而一个数字的幸运值取决于其数值和所在位置，可以用下表描述。例如，数字 $319$ 的幸运值为 $F_{2} + 3F_{0}$。  每只羊都希望在它写出的 $k$ 个整数中，使幸运值之和最大。你能帮帮它们吗？

第一行包含一个整数 $k$（$1 \leq k \leq 999999$），表示每只羊需要写的数字个数。 第二行包含六个整数 $F_0, F_1, F_2, F_3, F_4, F_5$（$1 \leq F_i \leq 10^9$），表示每个数字对应位置的幸运值。 第三行包含一个整数 $q$（$1 \leq q \leq 100\,000$），表示羊的数量。 接下来的 $q$ 行，每行包含一个整数 $n_i$（$1 \leq n_i \leq 999999$），表示第 $i$ 只羊需要写出的数字之和。

输出 $q$ 行，第 $i$ 行输出第 $i$ 只羊能获得的最大幸运值之和。

在第一个测试样例中，$57 = 9 + 9 + 39$。三个 $9$ 在个位上贡献 $1 \cdot 3$，$39$ 中十位上的 $3$ 贡献 $2 \cdot 1$，因此幸运值之和为 $11$。 在第二个测试样例中，$63 = 35 + 19 + 9$，幸运值之和为 $8$。 由 ChatGPT 4.1 翻译