## CCO '21 P2 - Weird Numeral System

View as PDF

Points: 17 (partial)
Time limit: 1.5s
Memory limit: 1G

Author:
Problem type
##### Canadian Computing Olympiad: 2021 Day 1, Problem 2

Alice enjoys thinking about base- numeral systems (don't we all?). As you might know, in the standard base- numeral system, an integer can be represented as where:

• Each digit is in the set , and
• .

For example, in standard base-3, you would write as 1 2 0, since .

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

A weird-base- system is just like the standard base- system, except that instead of using the digits , you use for some value . For example, in a weird-base-3 system with , you could write as 1 -1 -1 0, since .

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

#### Input Specification

The first line contains four space-separated integers, , , , and .

The second line contains distinct integers, through .

Finally, the -th of the next lines contains .

For 8 of the 25 available marks, .

#### Output Specification

Output lines, the -th of which is a weird-base- representation of . 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

We have:
,
, and
.

#### Sample Input 2

10 1 3 2
0 2 -2
17

#### Sample Output 2

IMPOSSIBLE