32570번 - Knitting 스페셜 저지다국어

문제

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.

Figure K.1: 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.

입력

• 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 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.

제한

힌트