题目描述

Alice 正在思考一个关于 $k$ 进制整数的问题。

普通的 $k$ 进制可以将整数 $n$ 表示为 $d_{m - 1} d_{m - 2} \cdots d_0$，且满足：

1. $0 \leq d_i < k$；
2. $n = \displaystyle\sum_{i = 0}^{m - 1} d_i k^i$。

然而，普通的 $k$ 进制整数对于 Alice 来说太简单了，Alice 更喜欢奇怪的 $k$ 进制整数。它与普通 $k$ 进制整数的差别仅仅在于将 $0 \leq d_i < k$ 换成了 $d_i \in a$，其中 $a$ 为一个长为 $D$ 的数列。

现在有一组固定的 $a_1, a_2, \cdots, a_D$，Alice 想要将 $q$ 个十进制整数 $n_1, n_2, \cdots, n_q$ 全部转化为奇怪的 $k$ 进制整数，这种问题显然更适合写程序来解决。

输入格式

第一行，四个整数 $k, q, D, M$；

第二行，$D$ 个整数 $a_1, a_2, \cdots, a_D$；

接下来 $q$ 行，每行一个整数 $n_i$。

输出格式

$q$ 行，第 $i$ 行表示 $n_i$ 转化后的结果，按幂次从高到低的顺序输出每一位，两个位之间用单个空格间隔。当 $a_i$ 中包含 $0$ 时，你转化的结果可以包含前导零，但最好不要太多；当 $n_i = 0$ 时，你转化的结果也不能为空。如果有多种方案可以随便输出一种，如果无法转化输出 IMPOSSIBLE。

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

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

10 1 3 2
0 2 -2
17

IMPOSSIBLE

提示

本题由

。

数据范围

对于 $100\%$ 的数据，$2 \leq k \leq 10^6$，$1 \leq q \leq 5$，$1 \leq D \leq 801$，$1 \leq M \leq 400$，$-M \leq a_i \leq M$，$-10^{18} \leq n_i \leq 10^{18}$。

题目来源

CCO2021 D1T2