100 atcoder#ARC144C. [ARC144C] K Derangement
[ARC144C] K Derangement
Score : points
Problem Statement
You are given positive integers and . Find the lexicographically smallest permutation of the integers from through that satisfies the following condition:
- for all ().
If there is no such permutation, print -1
.
What is lexicographical order on sequences?
The following is an algorithm to determine the lexicographical order between different sequences and .
Below, let denote the -th element of . Also, if is lexicographically smaller than , we will denote that fact as ; if is lexicographically larger than , we will denote that fact as .
- Let be the smaller of the lengths of and . For each , we check whether and are the same.
- If there is an such that , let be the smallest such . Then, we compare and . If is less than (as a number), we determine that and quit; if is greater than , we determine that and quit.
- If there is no such that , we compare the lengths of and . If is shorter than , we determine that and quit; if is longer than , we determine that and quit.
Constraints
Input
Input is given from Standard Input in the following format:
Output
Print the lexicographically smallest permutation of the integers from through that satisfies the condition, in the following format:
If there is no such permutation, print -1
.
3 1
2 3 1
Two permutations satisfy the condition: and . For instance, the following holds for :
8 3
4 5 6 7 8 1 2 3
8 6
-1