시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 1 1 1 100.000%

문제

Given a sequence $a$ consisting of integers $a_1, \ldots, a_n$, consider all its non-decreasing subsequences of length $k$. Among all of these take the one with smallest last element. We denote the value of this element with $s_k$.

The sequence $s(a) = s_1, \ldots, s_{l}$ is a sketch for sequence $a$, where $l$ is the length of the longest non-decreasing subsequence of $a$.

Building a sketch of the sequence is a standard task while finding the length of the longest non-decreasing subsequence. Here we consider an opposite problem: given a sketch with some missing entries, find any sequence producing this sketch.

Formally, you are given a sequence $t_1, \ldots, t_k$ where each element is either a positive integer or $-1$. You have to find a sequence $a_1, \ldots, a_n$ with each element being an integer between $1$ and $m$, inclusive, satisfying the following properties: length of the sketch of $a$ should be equal to $k$, and for each index $i$ between $1$ and $k$, if $t_i \neq -1$, then $s_i = t_i$ should hold.

입력

First line contains three integers $k$, $n$, $m$ ($1 \leq k \leq 300\,000$, $1 \leq n \leq 300\,000$, $1 \leq m \leq 10^9$), the length of the sketch, the length of the desired sequence and the upper bound on element values respectively.

Next line contains $k$ numbers $t_1, \ldots, t_k$ ($1 \leq t_i \leq m$ or $t_i = -1$), the sketch itself.

출력

If a sequence with such sketch exists, output the elements of a desired sequence. In case of multiple answers you may output any of them.

If no valid sequence exists, output a single integer $-1$.

예제 입력 1

3 4 10
3 7 7

예제 출력 1

3 7 8 7

예제 입력 2

3 5 10
3 -1 7

예제 출력 2

3 6 5 4 7

예제 입력 3

4 2 10
1 2 3 4

예제 출력 3

-1

힌트

Sketch of the answer sequence in example 2: $3\ 4\ 7$.