[AdditionalFile3578.zip](file://AdditionalFile3578.zip?type=additional_file)

#3578. 「CCO 2021」奇怪的数字系统

标签: 传统 | 时间限制: 1500 ms | 内存限制: 1024 MiB |

题目描述

译自 CCO 2021 Day1「Weird Numeral System」

Alice 喜欢思考 $K$ 进制数字系统。在标准的 $K$ 进制数字系统中，一个整数 $n$ 可以表示成 $d_{m-1}d_{m-2}\dots d_1d_0$，其中：

• 每个数位 $d_i$ 在集合 $\{0,1,\dots,K-1\}$ 中，且
• $d_{m-1}K^{m-1}+d_{m-2}K^{m-2}+\cdots+d_1K^1+d_0K^0=n$。

例如，在标准的 $3$ 进制中，你需要将 $15$ 写作 1 2 0，因为 $(1)⋅3^2+(2)⋅3^1+(0)⋅3^0=15$。

但标准的 $K$ 进制系统对 Alice 来说太简单了。她开始思考奇怪的 $K$ 进制系统。

这个奇怪的 $K$ 进制系统很像标准 $K$ 进制系统，但是它的每一位不是 $\{0,1,\dots,K-1\}$ 中选取的，而是 $\{a_1,a_2,\dots,a_D\}$。例如，一个奇怪 $3$ 进制系统，满足 $a=\{-1,0,1\}$，那么你可以将 $15$ 写作 1 -1 -1 0，因为 $(1)⋅3^3+(−1)⋅3^2+(−1)⋅3^1+(0)⋅3^0=15$。

Alice 现在有 $Q$ 个整数 $n_1$ 到 $n_Q$，她想知道如何将这些整数在一个使用 $a_1$ 到 $a_D$ 的奇怪 $K$ 进制系统中表示出来。帮帮她！

输入格式

第一行输入四个整数 $K,Q,D$ 和 $M$。

接下来一行输入 $D$ 个互异整数 $a_1$ 到 $a_D$。

接下来 $Q$ 行，其中第 $i$ 行输入一个整数 $n_i$。

输出格式

输出 $Q$ 行，第 $i$ 行输出 $n_i$ 的奇怪 $K$ 进制表示。如果有多解，输出任意一种。注意 $0$ 的表示需要至少一位。

如果 $n_i$ 无解，输出 IMPOSSIBLE。

样例 1

输入

3 3 3 1
-1 0 1
15
8
-5

输出

1 -1 -1 0
1 0 -1
-1 1 1

样例 2

输入

10 1 3 2
0 2 -2
17

输出

IMPOSSIBLE

数据范围与提示

对于 $100\%$ 的数据，保证 $2\le K\le 10^6$，$1\le Q\le 5$，$1\le D\le 5001$，$1\le M\le 2500$，$-M\le a_i\le M$，$-10^{18}\le n_i\le 10^{18}$。

对于 $32\%$ 的子任务，保证 $M=K-1\le 400, K=D\le 801$。