P7829 [CCO 2021] Weird Numeral System

Alice is thinking about a problem involving base $k$ integers. In standard base $k$, an integer $n$ can be written as $d_{m - 1} d_{m - 2} \cdots d_0$, satisfying: 1. $0 \leq d_i < k$. 2. $n = \displaystyle\sum_{i = 0}^{m - 1} d_i k^i$. However, standard base $k$ integers are too easy for Alice. Alice prefers weird base $k$ integers. The only difference from standard base $k$ integers is that the condition $0 \leq d_i < k$ is replaced by $d_i \in a$, where $a$ is a sequence of length $D$. Now, a fixed sequence $a_1, a_2, \cdots, a_D$ is given. Alice wants to convert $q$ decimal integers $n_1, n_2, \cdots, n_q$ into weird base $k$ integers. This kind of problem is clearly more suitable to be solved by writing a program.

The first line contains four integers $k, q, D, M$. The second line contains $D$ integers $a_1, a_2, \cdots, a_D$. The next $q$ lines each contain one integer $n_i$.

Output $q$ lines. The $i$-th line should be the result of converting $n_i$. Output each digit from the highest power to the lowest power, separated by a single space. When $a_i$ contains $0$, your result may contain leading zeros, but it is better not to have too many. When $n_i = 0$, your result must not be empty. If there are multiple valid answers, you may output any one of them. If it is impossible to convert, output `IMPOSSIBLE`.

**This problem is provided with an SPJ by @[Leasier](https://www.luogu.com.cn/user/201007).** #### Constraints For $100\%$ of the testdata, $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}$. #### Source [CCO2021](https://cemc.math.uwaterloo.ca/contests/computing/2021/index.html) D1T2. Translated by ChatGPT 5