Canadian Computing Olympiad: 2021 Day 1, Problem 2

Alice enjoys thinking about base-~K~ numeral systems (don't we all?). As you might know, in the standard base-~K~ numeral system, an integer ~n~ can be represented as ~d_{m-1} d_{m-2} \cdots d_1 d_0~ where:

• Each digit ~d_i~ is in the set ~\{0, 1, \dots, K-1\}~, and
• ~d_{m-1} K^{m-1} + d_{m-2} K^{m-2} + \cdots + d_1 K^1 + d_0 K^0 = n~.

For example, in standard base-3, you would write ~15~ as 1 2 0, since ~(1) \cdot 3^2 + (2) \cdot 3^1 + (0) \cdot 3^0 = 15~.

But standard base-~K~ systems are too easy for Alice. Instead, she's thinking about weird base-~K~ systems.

A weird-base-~K~ system is just like the standard base-~K~ system, except that instead of using the digits ~\{0, \dots, K-1\}~, you use ~\{a_1, a_2, \dots, a_D\}~ for some value ~D~. For example, in a weird-base-3 system with ~a = \{-1, 0, 1\}~, you could write ~15~ as 1 -1 -1 0, since ~(1) \cdot 3^3 + (-1) \cdot 3^2 + (-1) \cdot 3^1 + (0) \cdot 3^0 = 15~.

Alice is wondering how to write ~Q~ integers, ~n_1~ through ~n_Q~, in a weird-base-~K~ system that uses the digits ~a_1~ through ~a_D~. Please help her out!

Input Specification

The first line contains four space-separated integers, ~K~, ~Q~, ~D~, and ~M~ ~(2 \le K \le 1\,000\,000, 1 \le Q \le 5, 1 \le D \le 5\,001, 1 \le M \le 2500)~.

The second line contains ~D~ distinct integers, ~a_1~ through ~a_D~ ~(-M \le a_i \le M)~.

Finally, the ~i~-th of the next ~Q~ lines contains ~n_i~ ~(-10^{18} \le n_i \le 10^{18})~.

For 8 of the 25 available marks, ~M = K-1 \le 400, K = D \le 801~.

Output Specification

Output ~Q~ lines, the ~i~-th of which is a weird-base-~K~ representation of ~n_i~. If multiple representations are possible, any will be accepted. The digits of the representation should be separated by spaces. Note that 0 must be represented by a non-empty set of digits.

If there is no possible representation, output IMPOSSIBLE.

Sample Input 1

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

Sample Output 1

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

Explanation for Sample Output 1

We have:
~(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~, and
~(-1) \cdot 3^2 + (1) \cdot 3^1 + (1) \cdot 3^0 = -5~.

Sample Input 2

10 1 3 2
0 2 -2
17

Sample Output 2

IMPOSSIBLE