Coprime sequence
Statement
Goal
Given a sequence xs of n strictly positive integers, find the smallest lexicographic permutation such that every pair of consecutive numbers is coprime. If there is none printInput
Line 1 : An integer n.
Line 2 : The sequence xs, containing n space-separated integers.
Line 2 : The sequence xs, containing n space-separated integers.
Output
The smallest lexicographic permutation such that every pair of consecutive numbers (space-separated) is coprime, or -1 if there is none.
Constraints
0 < n < 16
0 < each integer in xs < 2 ** 64
0 < each integer in xs < 2 ** 64
Example
Input
3 1 2 4
Output
2 1 4
Tags
Difficulty
Hard
Test cases
1. Base Test
Input
3
1 2 4
Output
2 1 4
1. Base val Validator
Input
3
25 2 5
Output
5 2 25
2. Repeated Test
Input
3
1 2 2
Output
2 1 2
2. Repeated Validator
Input
3
7 7 5
Output
7 5 7
3. Repeated special Test
Input
3
1 1 1
Output
1 1 1
3. Repeated special val Validator
Input
5
1 1 1 1 1
Output
1 1 1 1 1
4. None Test
Input
4
1 2 4 8
Output
-1
4. None val Validator
Input
3
6 6 6
Output
-1
5. Already fine Test
Input
3
7 11 43
Output
7 11 43
5. Already fine val Validator
Input
3
2 1 4
Output
2 1 4
6. Cubic Test
Input
8
210 46189 41354 717541 519961 78387 183065 494543
Output
210 46189 41354 183065 494543 519961 78387 717541
6. Cubic val Validator
Input
8
21210 717541 41354 183065 78387 519961 494543 46189
Output
21210 46189 41354 183065 494543 519961 78387 717541
7. No bfs Test
Input
11
16 31 24 30 17 9 10 11 37 23 36
Output
9 10 11 16 17 23 24 31 30 37 36
7. No bfs val Validator
Input
11
12 37 34 29 3 23 27 17 8 33 10
Output
3 8 17 10 23 12 29 27 34 33 37
8. No bruteforce Test
Input
12
25 13 12 19 46 10 49 32 41 2 56 48
Output
-1
8. No bruteforce val Validator
Input
11
20 22 28 54 55 56 40 32 24 6 36
Output
-1
9. 1 to the end Test
Input
12
406158566653369438 1 111 2263 205 2059 301 1541 517 1159 689 1003
Output
111 205 301 517 689 1003 1159 1541 2059 2263 1 406158566653369438
9. 1 to the end val Validator
Input
12
406158566653369438 1 205 10767 301 2263 517 2059 689 1541 1003 1159
Output
205 301 517 689 1003 1159 1541 2059 2263 10767 1 406158566653369438
10. Archimedean solid Test
Input
12
61175409274934 26767617044195557 2950107827478559 242308091349447 6440343237770491 6489660668866939 3143836267621543 3359814435017 62251769470130099 9699690 591853121812345 729345064647247
Output
9699690 3359814435017 729345064647247 61175409274934 242308091349447 591853121812345 6440343237770491 2950107827478559 3143836267621543 62251769470130099 6489660668866939 26767617044195557
10. Archimedean solid val Validator
Input
12
61175409274934 26767617044195557 2950107827478559 242308091349447 6440343237770491 6489660668866939 3143836267621543 3359814435017 62251769470130099 6877080210 591853121812345 729345064647247
Output
6877080210 3359814435017 729345064647247 61175409274934 242308091349447 591853121812345 6440343237770491 2950107827478559 3143836267621543 62251769470130099 6489660668866939 26767617044195557
11. N = 15 Random unique solvable Test
Input
15
378 641 390 563 414 523 440 401 525 668 321 634 477 458 597
Output
321 401 378 523 390 563 414 641 440 477 458 525 634 597 668
11. N = 15 Random unique solvable val Validator
Input
15
21 32 37 23 40 34 27 16 11 5 8 29 19 24 2
Output
2 5 8 11 16 19 21 23 24 29 32 27 34 37 40
12. N = 15 Random unique unsolvable Test
Input
15
21 36 11 26 15 5 40 8 33 20 34 17 6 18 30
Output
-1
12. N = 15 Random unique unsolvable val Validator
Input
15
10 24 36 2 16 1 4 31 37 7 14 3 38 21 6
Output
-1
13. N = 15 Random non unique solvable Test
Input
15
12 1 30 1 36 1 21 37 20 31 38 29 33 17 7
Output
1 1 1 7 12 17 20 21 29 30 31 33 38 37 36
13. N = 15 Random non unique solvable val Validator
Input
15
38 1 2 17 5 24 8 9 27 10 2 23 37 40 18
Output
2 1 2 5 8 9 10 17 18 23 24 37 38 27 40
14. 1 to the end Test
Input
15
1 3 2 3 2 3 2 3 2 3 2 3 2 3 6
Output
3 2 3 2 3 2 3 2 3 2 3 2 3 1 6
14. 1 to the end Validator
Input
15
1 7 4 7 4 7 4 7 4 7 4 7 4 7 14
Output
7 4 7 4 7 4 7 4 7 4 7 4 7 1 14
Solution language
Solution
Stub generator input