21824번 - Weird Numeral System 스페셜 저지다국어

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 . . . d₁ d₀ where:

• Each digit d_i is in the set {0, 1, . . . , K − 1}, and
• d_m−1K^m−1 + d_m−2K^m−2 + · · · + d₁K¹ + d₀K⁰ = n.

For example, in standard base-3, you would write 15 as 1 2 0, since (1) · 3² + (2) · 3¹ + (0) · 3⁰ = 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, . . . , K − 1}, you use {a₁, a₂, . . . , 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) · 3³ + (−1) · 3² + (−1) · 3¹ + (0) · 3⁰ = 15.

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

The first line contains four space-separated integers, K, Q, D, and M (2 ≤ K ≤ 1 000 000, 1 ≤ Q ≤ 5, 1 ≤ D ≤ 5001, 1 ≤ M ≤ 2500).

The second line contains D distinct integers, a₁ through a_D (−M ≤ a_i ≤ M).

Finally, the i-th of the next Q lines contains n_i (−10¹⁸ ≤ n_i ≤ 10¹⁸).

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.