题目描述

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)\cdot 3^2+(2)\cdot 3^1+(0)\cdot 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)\cdot 3^3+(-1)\cdot 3^2+(-1)\cdot 3^1+(0)\cdot 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$。

---