暂无测试数据。

蒜头君的种植事业蒸蒸日上，它准备大范围种植魔法豆，原本春天种一颗魔法豆，秋天也只能收获一颗魔法豆，显然不太划算。但是蒜头君有 $1000$ 个魔法盆，依次编号为 $1,\ 2,\ 3 \cdots 999,\ 1000$，可以让魔法豆的产量是原来的产量乘以 $1,\ k,\ k^2,\ k^3,\ k^4 \cdots\ k^{998},\ k^{999} $。但是魔法盆有一个种植限制，每个盆中种植的魔法豆数目必须严格小于 $k$。

蒜头君目前的种植情况用一个不超过 $1000$ 位的数字表示，该数字的每一位从左到右依次为编号 $1,\ 2,\ 3 \cdots 999,\ 1000$ 的盆中种植魔法豆的数目，如果第 $i$ 个魔法盆及之后的所有魔法盆都没有种植，就只显示前 $i - 1$ 个魔法盆的种植情况。

农业魔法部给蒜头君提出了 $Q$ 个增产计划，请问想要分别满足每个增产计划，蒜头君应该如何种植魔法豆。

输入格式

输入有 $Q + 2$ 行：

• 第一行是一个长度为 $1000$ 的整数，该整数的每一位从左到右依次为编号 $1,\ 2,\ 3 \cdots 999,\ 1000$ 的盆中目前种植魔法豆的数目 (每一位都严格小于k)。
• 第二行是两个空格隔开的整数，分别为 $k$ 和 $Q$（$2 \leq k \leq 10,\ 1 \leq Q \leq 10^3$）；
• 接下来的 $Q$ 行，每行有一个整数 $a_i$（$1 \leq a_i \leq 10^9$），代表每一个增加的产量, 所有的增产计划都是相互独立的, 不累加增产。

输出格式

输出为 $Q$ 行，每行是一个整数，保证该整数位数不超过 $1000$ 位，该整数每一位从左到右依次为编号 $1,\ 2,\ 3 \cdots\ 999,\ 1000$ 的盆中种植魔法豆的数目，表示用这样的方式种植能满足增产计划, 如果第 $i$ 个魔法盆及之后的所有魔法盆都没有种植，就只显示前 $i - 1$ 个魔法盆的种植情况。

数据规模与约定

111
2 3
1
2
3

0001
1001
0101