Weird Numeral System

Η Alice απολαμβάνει να σκέφτεται αριθμητικά συστήματα με βάση το ~K~ (όπως όλοι μας, έτσι δεν είναι;). Όπως μπορεί να ξέρετε, στο τυπικό αριθμητικό σύστημα με βάση το ~K~, ένας ακέραιος ~n~ μπορεί να αναπαρασταθεί ως ~d_{m-1}~ ~d_{m-2}~ ... ~d_1~ ~d_0~ όπου:

• Κάθε ψηφίο ~d_i~ ανήκει στο σύνολο {~0~,~1~, ..., ~K - 1~} και

• ~d_{m-1}K^{m-1} + d_{m-2}K^{m-2} + d_1K^1 + d_0K^0 = n~.

Για παράδειγμα, στην τυπικό σύστημα με βάση το ~3~, θα γράφατε το ~15~ ως ~1~ ~2~ ~0~ καθώς ~(1)~ ~\cdot~ ~3^2~ + ~(2)~ ~\cdot~ ~3^1~ + ~(0)~ ~\cdot~ ~3^0~ = ~15~.

Αλλά τα τυπικά αριθμητικά συστήματα με βάση το ~K~ είναι πολύ εύκολα για την Alice. Αντ' αυτού, σκέφτεται περίεργα αριθμητικά συστήματα με βάση το ~K~.

Ένα περίεργο αριθμητικό συστήμα με βάση το ~K~ είναι σαν το τυπικό αριθμητικό συστήμα με βάση το ~K~, με τη διαφορά ότι αντί να χρησιμοποιείτε τα ψηφία {~0~,~1~, ..., ~K - 1~}, χρησιμοποιείτε {~a_1~,~a_2~, ..., ~a_D~} για κάποια τιμή ~D~. Για παράδεγμα, σε ένα περίεργο αριθμητικό συστήμα με βάση το ~3~ με ~a~ = {~-1~,~0~,~1~}, θα μπορούσατε να γράψετε το ~15~ ως ~1~ ~-1~ ~-1~ ~0~ καθώς ~(1)~ ~\cdot~ ~3^3~ + ~(-1)~ ~\cdot~ ~3^2~ + ~(-1)~ ~\cdot~ ~3^1~ + ~(0)~ ~\cdot~ ~3^0~ = ~15~.

Η Alice αναρωτιέται πως να γράψει ~Q~ ακέραιους από το ~n_1~ έως το ~n_Q~, σε ένα περίεργο αριθμητικό συστήμα με βάση το ~K~ που χρησιμοποιεί τα ψηφία ~a_1~ έως ~a_D~. Παρακαλώ βοηθήστε την!

Είσοδος

Η πρώτη γραμμή περιέχει τέσσερις ακέραιους χωρισμένους με κενό, ~K~, ~Q~, ~D~ και ~M~ (~2~ ~\le~ ~K~ ~\le~ ~1\,000\,000~, ~1~ ~\le~ ~Q~ ~\le~ ~5~, ~1~ ~\le~ ~D~ ~\le~ ~5\,001~, ~1~ ~\le~ ~M~ ~\le~ ~2\,500~).

Η δεύτερη γραμμή περιέχει ~D~ μοναδικούς ακέραιους, ~a_1~ έως ~a_D~ (-~M~ ~\le~ ~a_i~ ~\le~ ~M~).

Τέλος, η ~i~-οστη από τις επόμενες ~Q~ γραμμές περιέχει ~n_i~ (-~10^{18}~).

Βαθμολογία

Για ~8~ από τους ~25~ διαθέσιμους βαθμούς, ~M~ = ~K - 1~ ~\le~ ~400~, ~K~ = ~D~ ~\le~ ~801~.

Έξοδος

Εκτυπώστε ~Q~ γραμμές, η ~i~-οστη από τις οποίες είναι μια αναπαράσταση του ~n_i~ σε ένα περίεργο αριθμητικό συστήμα με βάση το ~K~. Αν υπάρχουν πολλαπλές δυνατές αναπαραστάσεις, οποιαδήποτε από αυτές θα γίνει δεκτή. Τα ψηφία της αναπαράστασης θα πρέπει να είναι χωρισμένα με κενό. Σημειώστε ότι το ~0~ πρέπει να αναπαραστάται ως ένα μη κενό σύνολο ψηφίων.

Αν δεν υπάρχουν δυνατές αναπαραστάσεις, εκτυπώστε IMPOSSIBLE.

Παραδείγματα

input

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

output

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

Επεξήγηση του 1ου παραδείγματος

Έχουμε: ~(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~ και

~(-1)~ ~\cdot~ ~3^2~ + ~(1)~ ~\cdot~ ~3^1~ + ~(1)~ ~\cdot~ ~3^0~ = ~-5~.

input

10 1 3 2
0 2 -2
17

output

IMPOSSIBLE