K. Knitting
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are knitting a scarf in a striped pattern, having made strong progress on the first few stripes. You have multiple colours available to continue creating the pattern and would very much like that no colour appears too often – more specifically, that the colour appearing most often still appears as few times as possible.

A knitted solution to sample input 1. No colour is used more than twice, nor is any colour repeated within 3 consecutive stripes.

Please extend the given design to fashion a nice scarf.

Input

  • One line containing the number of stripes to create, $$$n$$$, the number of colours available, $$$k$$$, and the minimum spacing between stripes of the same colour, $$$p$$$ ($$$1 \le n, k, p \le 10^5$$$).
  • One line containing the number of stripes already knitted, $$$m$$$ ($$$1 \le m \le n$$$).
  • One line containing $$$m$$$ integers, the colours of the stripes $$$s_i$$$ ($$$1 \le s \le k$$$).

The colours of the stripes are represented as integers in $$$[1{\ldots}k]$$$.

Output

Output any stripe pattern starting with $$$s_{1 \ldots m}$$$ that does not repeat any of the colours too soon and uses the most-frequent colour as few times as possible.

If it is not possible to create a scarf from the parameters, output impossible instead.

Examples
Input
10 6 3
4
4 1 6 4
Output
4 1 6 4 1 5 2 3 6 5
Input
5 2 3
2
1 2
Output
impossible
Input
2 2 3
1
2
Output
2 1
Input
10 26 5
4
8 3 16 3
Output
impossible