Problem Description

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.

Input Format

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 Format

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.

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

Hint

**This problem is provided with an SPJ by

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 D1T2.

Translated by ChatGPT 5