Canadian Computing Competition: 2022 Stage 1, Senior #3
You are composing music for the Cool Clarinet Competition (CCC). You have been instructed to make a piece of music with exactly 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, , , and are samples of . Note that is not a sample of . 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 . Second, they want a piece with exactly good samples.
Can you construct a piece to satisfy the clarinet players?
The first and only line of input will contain space-separated integers, , , and .
The following table shows how the available 15 marks are distributed.
|Marks Awarded||Bounds on||Bounds on||Bounds on|
If there is a piece of music that satisfies the given constraints, output integers between and , representing the pitches of the notes of the piece of music. If there is more than one such piece of music, any such piece of music may be outputted.
Otherwise, output .
Sample Input 1
3 2 5
Sample Output 1
1 2 1
Explanation of Output for Sample Input 1
Notice that the piece is composed of notes, each of which is one of possible pitches, and . That piece of music has a total of samples, but only good samples: , , , , . Notice that the two good samples of are different since they start at two different positions.
Note that the piece is the only other valid output for this input.
One example of an output that would be incorrect is , since it has notes with pitches larger than . Another incorrect output would be , since it only has four good samples: , , , and .
Sample Input 2
5 5 14
Sample Output 2
1 5 3 2 1
Explanation of Output for Sample Input 2
The 14 good samples are: , , , , , , , , , , , , , .
Sample Input 3
5 5 50
Sample Output 3
Explanation of Output for Sample Input 3
There are no pieces with notes that can produce different good samples.