Remote Training on Programming

Задана последовательность из N целых чисел. Числа, равные нулю вы должны поменять на какие-то целые из диапазона от 1 до 10⁹. Будем считать последовательность правильной, если расстояние между любой парой одинаковых чисел более K. Расстояние между соседними числами равно 1. Ваша задача получить M-ую в лексикографическом порядке правильную последовательность. Либо определить, что такой не существует.

 

Формат входного файла

 

В первой строке входного файла содержатся 3 целых числа N, K и M (1<=N <=2*10⁵, 0<=K<=N, 1<=M<=10⁸).

В следующей строке входного файла содержится N целых чисел в промежутке от 0 до 10⁹ включительно, разделенных пробелом.

 

Формат выходного файла

 

Выведите N целых чисел – требуемую последовательность. Если решения не существует, выведите -1.

Пример

Входные данные	Выходные данные
2 2 1 1 2	1 2
2 2 2 1 2	-1
2 2 2 2 2	-1
3 2 1 0 0 1	2 3 1