Alice 喜欢研究 $K$ 进制计数系统。众所周知，在标准的 $K$ 进制系统中，一个整数 $n$ 可以表示为 $d_{m-1} d_{m-2} \dots d_1 d_0$，其中：

• 每个数位 $d_i$ 都在集合 $\{0, 1, \dots, K - 1\}$ 中，且
• $d_{m-1}K^{m-1} + d_{m-2}K^{m-2} + \dots + 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, \dots, K - 1\}$，而是使用集合 $\{a_1, a_2, \dots, a_D\}$ 中的数字。例如，在 $a = \{-1, 0, 1\}$ 的怪异 3 进制系统中，15 可以写成 1 -1 -1 0，因为 $(1) \cdot 3^3 + (-1) \cdot 3^2 + (-1) \cdot 3^1 + (0) \cdot 3^0 = 15$。

Alice 想知道如何用使用数字 $a_1$ 到 $a_D$ 的怪异 $K$ 进制系统来表示 $Q$ 个整数 $n_1$ 到 $n_Q$。请帮帮她！

输入格式

第一行包含四个空格分隔的整数 $K, Q, D$ 和 $M$ ($2 \le K \le 1\,000\,000, 1 \le Q \le 5, 1 \le D \le 5001, 1 \le M \le 2500$)。

第二行包含 $D$ 个不同的整数 $a_1$ 到 $a_D$ ($-M \le a_i \le M$)。

最后，接下来的 $Q$ 行中，第 $i$ 行包含 $n_i$ ($-10^{18} \le n_i \le 10^{18}$)。

对于 25 分中的 8 分，满足 $M = K - 1 \le 400, K = D \le 801$。

输出格式

输出 $Q$ 行，第 $i$ 行应为 $n_i$ 的怪异 $K$ 进制表示。如果存在多种表示方式，输出任意一种即可。表示中的数字应以空格分隔。注意，0 必须由非空的数字序列表示。

如果不存在可能的表示，输出 IMPOSSIBLE。

样例

样例输入 1

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

样例输出 1

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

说明

我们有： $(1) \cdot 3^3 + (-1) \cdot 3^2 + (-1) \cdot 3^1 + (0) \cdot 3^0 = 15$, $(1) \cdot 3^2 + (0) \cdot 3^1 + (-1) \cdot 3^0 = 8$, 且 $(-1) \cdot 3^2 + (1) \cdot 3^1 + (1) \cdot 3^0 = -5$。

样例输入 2

10 1 3 2
0 2 -2
17

样例输出 2

IMPOSSIBLE