Good Samples

Time limit1sMemory limit1024 MB

Summary

Given N, M, and K, build a sequence of N pitches in 1 to M with exactly K subarrays that have no repeated values, or report -1.

Level: Medium6 of 10
Topics: Sliding window, Math, Implementation, Array
Solved: No attempts yet

Problem

You are composing music for the Cool Clarinet Competition (CCC). You have been instructed to make a piece of music with exactly $N$ notes. A note is represented as a positive integer, indicating the pitch of the note.

We call a non-empty sequence of consecutive notes in the piece a sample. For instance, (3, 4, 2), (1, 2, 3, 4, 2) and (4) are samples of 1, 2, 3, 4, 2. Note that (1, 3) is not a sample of 1, 2, 3, 4, 2. We call two samples different if they start or end at a different position in the piece.

We call a sample good if no two notes in the sample have the same pitch.

The clarinet players are picky in two ways. First, they will not play any note with pitch higher than $M$ . Second, they want a piece with exactly $K$ good samples.

Can you construct a piece to satisfy the clarinet players?

Input

The first and only line of input contains three space-separated integers, $N$ , $M$ and $K$ .

Output

If there is a piece of music that satisfies the given constraints, output $N$ integers between 1 and $M$ , representing the pitches of the notes of the piece of music. If there is more than one such piece of music, you may output any of them.

Otherwise, output -1.

Examples3

Example 1
Input
```
3 2 5
```
Expected output
```
1 2 1
```
Example 2
Input
```
5 5 14
```
Expected output
```
1 5 3 2 1
```
Example 3
Input
```
5 5 50
```
Expected output
```
-1
```