405906: GYM102155 H Sketch

Memory Limit:512 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

H. Sketchtime limit per test1 secondmemory limit per test512 megabytesinputstandard inputoutputstandard output

Given a sequence a consisting of integers a1, ..., an, 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 sk.

The sequence s(a) = s1, ..., sl 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 t1, ..., tk where each element is either a positive integer or  - 1. You have to find a sequence a1, ..., an 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 ti ≠  - 1, then si = ti should hold.

Input

First line contains three integers k, n, m (1 ≤ k ≤ 300 000, 1 ≤ n ≤ 300 000, 1 ≤ m ≤ 109), the length of the sketch, the length of the desired sequence and the upper bound on element values respectively.

Next line contains k numbers t1, ..., tk (1 ≤ ti ≤ m or ti =  - 1), the sketch itself.

Output

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.

ExamplesInput
3 4 10
3 7 7
Output
3 7 8 7
Input
3 5 10
3 -1 7
Output
3 6 5 4 7
Input
4 2 10
1 2 3 4
Output
-1
Note

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

加入题单

上一题 下一题 算法标签: