use rand::distributions::{Distribution, Uniform};
use std::io::BufRead;
use std::str::FromStr;
static TWINS: &'static [usize] = &[
3, 5, 11, 17, 29, 41, 59, 71, 101, 107, 137, 149, 179, 191, 197, 227, 239, 269, 281, 311, 347,
419, 431, 461, 521, 569, 599, 617, 641, 659, 809, 821, 827, 857, 881, 1019, 1031, 1049, 1061,
1091, 1151, 1229, 1277, 1289, 1301, 1319, 1427, 1451, 1481, 1487, 1607, 1619, 1667, 1697, 1721,
1787, 1871, 1877, 1931, 1949, 1997,
];
fn rec(n: usize, used: &mut [bool], res: &mut Vec<usize>) -> bool {
let i = res.len();
let l = 2 * i + 1;
let r = l + 2;
let twins = TWINS.iter().copied();
for twin in twins {
if twin < r {
continue;
}
let mid = twin - l;
// Because twin and twin+2 are primes, l+mid=twin and r+mid=twin+2 are primes
if mid > n || used[mid] {
continue;
}
let mut added = 0;
while 2 * added < mid && !used[mid - 2 * added] {
used[mid - 2 * added] = true;
res.push(mid - 2 * added);
added += 1;
if 2 * i + 2 * added + 1 >= n {
return true;
}
}
if rec(n, used, res) {
return true;
}
for add in 0..added {
used[mid - 2 * add] = false;
res.pop();
}
}
false
}
fn solve(n: usize) -> Vec<usize> {
let mut even: Vec<usize> = Vec::new();
let mut used = vec![false; n + 1];
if n > 0 {
even = [
1, 4, 3, 2, 5, 6, 7, 10, 9, 8, 11, 18, 13, 16, 15, 14, 17, 12, 19, 22, 21, 20, 23, 36,
25, 34, 27, 32, 29, 30, 31, 28, 33, 26, 35, 24, 37, 64, 39, 62, 41, 60, 43, 58, 45, 56,
47, 54, 49, 52, 51, 50, 53, 48, 55, 46, 57, 44, 59, 42, 61, 40, 63, 38, 65, 72, 67, 70,
69, 68, 71, 66, 73, 76, 75, 74, 77, 102, 79, 100, 81, 98, 83, 96, 85, 94, 87, 92, 89,
90, 91, 88, 93, 86, 95, 84, 97, 82, 99, 80, 101, 78, 103, 124, 105, 122, 107, 120, 109,
118, 111, 116, 113, 114, 115, 112, 117, 110, 119, 108, 121, 106, 123, 104, 125, 144,
127, 142, 129, 140, 131, 138, 133, 136, 135, 134, 137, 132, 139, 130, 141, 128, 143,
126, 145, 166, 147, 164, 149, 162, 151, 160, 153, 158, 155, 156, 157, 154, 159, 152,
161, 150, 163, 148, 165, 146, 167, 180, 169, 178, 171, 176, 173, 174, 175, 172, 177,
170, 179, 168, 181, 238, 183, 236, 185, 234, 187, 232, 189, 230, 191, 228, 193, 226,
195, 224, 197, 222, 199, 220, 201, 218, 203, 216, 205, 214, 207, 212, 209, 210, 211,
208, 213, 206, 215, 204, 217, 202, 219, 200, 221, 198, 223, 196, 225, 194, 227, 192,
229, 190, 231, 188, 233, 186, 235, 184, 237, 182, 239, 282, 241, 280, 243, 278, 245,
276, 247, 274, 249, 272, 251, 270, 253, 268, 255, 266, 257, 264, 259, 262, 261, 260,
263, 258, 265, 256, 267, 254, 269, 252, 271, 250, 273, 248, 275, 246, 277, 244, 279,
242, 281, 240, 283, 286, 285, 284, 287, 312, 289, 310, 291, 308, 293, 306, 295, 304,
297, 302, 299, 300, 301, 298, 303, 296, 305, 294, 307, 292, 309, 290, 311, 288, 313,
328, 315, 326, 317, 324, 319, 322, 321, 320, 323, 318, 325, 316, 327, 314, 329, 330,
331, 490, 333, 488, 335, 486, 337, 484, 339, 482, 341, 480, 343, 478, 345, 476, 347,
474, 349, 472, 351, 470, 353, 468, 355, 466, 357, 464, 359, 462, 361, 460, 363, 458,
365, 456, 367, 454, 369, 452, 371, 450, 373, 448, 375, 446, 377, 444, 379, 442, 381,
440, 383, 438, 385, 436, 387, 434, 389, 432, 391, 430, 393, 428, 395, 426, 397, 424,
399, 422, 401, 420, 403, 418, 405, 416, 407, 414, 409, 412, 411, 410, 413, 408, 415,
406, 417, 404, 419, 402, 421, 400, 423, 398, 425, 396, 427, 394, 429, 392, 431, 390,
433, 388, 435, 386, 437, 384, 439, 382, 441, 380, 443, 378, 445, 376, 447, 374, 449,
372, 451, 370, 453, 368, 455, 366, 457, 364, 459, 362, 461, 360, 463, 358, 465, 356,
467, 354, 469, 352, 471, 350, 473, 348, 475, 346, 477, 344, 479, 342, 481, 340, 483,
338, 485, 336, 487, 334, 489, 332, 491, 528, 493, 526, 495, 524, 497, 522, 499, 520,
501, 518, 503, 516, 505, 514, 507, 512, 509, 510, 511, 508, 513, 506, 515, 504, 517,
502, 519, 500, 521, 498, 523, 496, 525, 494, 527, 492, 529, 562, 531, 560, 533, 558,
535, 556, 537, 554, 539, 552, 541, 550, 543, 548, 545, 546, 547, 544, 549, 542, 551,
540, 553, 538, 555, 536, 557, 534, 559, 532, 561, 530, 563, 588, 565, 586, 567, 584,
569, 582, 571, 580, 573, 578, 575, 576, 577, 574, 579, 572, 581, 570, 583, 568, 585,
566, 587, 564, 589, 640, 591, 638, 593, 636, 595, 634, 597, 632, 599, 630, 601, 628,
603, 626, 605, 624, 607, 622, 609, 620, 611, 618, 613, 616, 615, 614, 617, 612, 619,
610, 621, 608, 623, 606, 625, 604, 627, 602, 629, 600, 631, 598, 633, 596, 635, 594,
637, 592, 639, 590, 641, 648, 643, 646, 645, 644, 647, 642, 649, 652, 651, 650, 653,
666, 655, 664, 657, 662, 659, 660, 661, 658, 663, 656, 665, 654, 667, 760, 669, 758,
671, 756, 673, 754, 675, 752, 677, 750, 679, 748, 681, 746, 683, 744, 685, 742, 687,
740, 689, 738, 691, 736, 693, 734, 695, 732, 697, 730, 699, 728, 701, 726, 703, 724,
705, 722, 707, 720, 709, 718, 711, 716, 713, 714, 715, 712, 717, 710, 719, 708, 721,
706, 723, 704, 725, 702, 727, 700, 729, 698, 731, 696, 733, 694, 735, 692, 737, 690,
739, 688, 741, 686, 743, 684, 745, 682, 747, 680, 749, 678, 751, 676, 753, 674, 755,
672, 757, 670, 759, 668, 761, 846, 763, 844, 765, 842, 767, 840, 769, 838, 771, 836,
773, 834, 775, 832, 777, 830, 779, 828, 781, 826, 783, 824, 785, 822, 787, 820, 789,
818, 791, 816, 793, 814, 795, 812, 797, 810, 799, 808, 801, 806, 803, 804, 805, 802,
807, 800, 809, 798, 811, 796, 813, 794, 815, 792, 817, 790, 819, 788, 821, 786, 823,
784, 825, 782, 827, 780, 829, 778, 831, 776, 833, 774, 835, 772, 837, 770, 839, 768,
841, 766, 843, 764, 845, 762, 847, 850, 849, 848, 851, 870, 853, 868, 855, 866, 857,
864, 859, 862, 861, 860, 863, 858, 865, 856, 867, 854, 869, 852, 871, 1000, 873, 998,
875, 996, 877, 994, 879, 992, 881, 990, 883, 988, 885, 986, 887, 984, 889, 982, 891,
980, 893, 978, 895, 976, 897, 974, 899, 972, 901, 970, 903, 968, 905, 966, 907, 964,
909, 962, 911, 960, 913, 958, 915, 956, 917, 954, 919, 952, 921, 950, 923, 948, 925,
946, 927, 944, 929, 942, 931, 940, 933, 938, 935, 936, 937, 934, 939, 932, 941, 930,
943, 928, 945, 926, 947, 924, 949, 922, 951, 920, 953, 918, 955, 916, 957, 914, 959,
912, 961, 910, 963, 908, 965, 906, 967, 904, 969, 902, 971, 900, 973, 898, 975, 896,
977, 894, 979, 892, 981, 890, 983, 888, 985, 886, 987, 884, 989, 882, 991, 880, 993,
878, 995, 876, 997, 874, 999, 872,
]
.into_iter()
.skip(1)
.step_by(2)
.copied()
.take_while(|v| *v + 300 < n)
.collect();
for e in &even {
used[*e] = true;
}
}
if !rec(n, &mut used, &mut even) {
even = [
1, 2, 3, 8, 5, 6, 7, 4, 9, 20, 11, 18, 13, 16, 15, 14, 17, 12, 19, 10, 21, 38, 23, 36,
25, 34, 27, 32, 29, 30, 31, 28, 33, 26, 35, 24, 37, 22, 39, 62, 41, 60, 43, 58, 45, 56,
47, 54, 49, 52, 51, 50, 53, 48, 55, 46, 57, 44, 59, 42, 61, 40, 63, 74, 65, 72, 67, 70,
69, 68, 71, 66, 73, 64, 75, 104, 77, 102, 79, 100, 81, 98, 83, 96, 85, 94, 87, 92, 89,
90, 91, 88, 93, 86, 95, 84, 97, 82, 99, 80, 101, 78, 103, 76, 105, 122, 107, 120, 109,
118, 111, 116, 113, 114, 115, 112, 117, 110, 119, 108, 121, 106, 123, 146, 125, 144,
127, 142, 129, 140, 131, 138, 133, 136, 135, 134, 137, 132, 139, 130, 141, 128, 143,
126, 145, 124, 147, 200, 149, 198, 151, 196, 153, 194, 155, 192, 157, 190, 159, 188,
161, 186, 163, 184, 165, 182, 167, 180, 169, 178, 171, 176, 173, 174, 175, 172, 177,
170, 179, 168, 181, 166, 183, 164, 185, 162, 187, 160, 189, 158, 191, 156, 193, 154,
195, 152, 197, 150, 199, 148, 201, 218, 203, 216, 205, 214, 207, 212, 209, 210, 211,
208, 213, 206, 215, 204, 217, 202, 219, 242, 221, 240, 223, 238, 225, 236, 227, 234,
229, 232, 231, 230, 233, 228, 235, 226, 237, 224, 239, 222, 241, 220, 243, 398, 245,
396, 247, 394, 249, 392, 251, 390, 253, 388, 255, 386, 257, 384, 259, 382, 261, 380,
263, 378, 265, 376, 267, 374, 269, 372, 271, 370, 273, 368, 275, 366, 277, 364, 279,
362, 281, 360, 283, 358, 285, 356, 287, 354, 289, 352, 291, 350, 293, 348, 295, 346,
297, 344, 299, 342, 301, 340, 303, 338, 305, 336, 307, 334, 309, 332, 311, 330, 313,
328, 315, 326, 317, 324, 319, 322, 321, 320, 323, 318, 325, 316, 327, 314, 329, 312,
331, 310, 333, 308, 335, 306, 337, 304, 339, 302, 341, 300, 343, 298, 345, 296, 347,
294, 349, 292, 351, 290, 353, 288, 355, 286, 357, 284, 359, 282, 361, 280, 363, 278,
365, 276, 367, 274, 369, 272, 371, 270, 373, 268, 375, 266, 377, 264, 379, 262, 381,
260, 383, 258, 385, 256, 387, 254, 389, 252, 391, 250, 393, 248, 395, 246, 397, 244,
399, 410, 401, 408, 403, 406, 405, 404, 407, 402, 409, 400, 411, 416, 413, 414, 415,
412, 417, 440, 419, 438, 421, 436, 423, 434, 425, 432, 427, 430, 429, 428, 431, 426,
433, 424, 435, 422, 437, 420, 439, 418, 441, 578, 443, 576, 445, 574, 447, 572, 449,
570, 451, 568, 453, 566, 455, 564, 457, 562, 459, 560, 461, 558, 463, 556, 465, 554,
467, 552, 469, 550, 471, 548, 473, 546, 475, 544, 477, 542, 479, 540, 481, 538, 483,
536, 485, 534, 487, 532, 489, 530, 491, 528, 493, 526, 495, 524, 497, 522, 499, 520,
501, 518, 503, 516, 505, 514, 507, 512, 509, 510, 511, 508, 513, 506, 515, 504, 517,
502, 519, 500, 521, 498, 523, 496, 525, 494, 527, 492, 529, 490, 531, 488, 533, 486,
535, 484, 537, 482, 539, 480, 541, 478, 543, 476, 545, 474, 547, 472, 549, 470, 551,
468, 553, 466, 555, 464, 557, 462, 559, 460, 561, 458, 563, 456, 565, 454, 567, 452,
569, 450, 571, 448, 573, 446, 575, 444, 577, 442, 579, 650, 581, 648, 583, 646, 585,
644, 587, 642, 589, 640, 591, 638, 593, 636, 595, 634, 597, 632, 599, 630, 601, 628,
603, 626, 605, 624, 607, 622, 609, 620, 611, 618, 613, 616, 615, 614, 617, 612, 619,
610, 621, 608, 623, 606, 625, 604, 627, 602, 629, 600, 631, 598, 633, 596, 635, 594,
637, 592, 639, 590, 641, 588, 643, 586, 645, 584, 647, 582, 649, 580, 651, 668, 653,
666, 655, 664, 657, 662, 659, 660, 661, 658, 663, 656, 665, 654, 667, 652, 669, 758,
671, 756, 673, 754, 675, 752, 677, 750, 679, 748, 681, 746, 683, 744, 685, 742, 687,
740, 689, 738, 691, 736, 693, 734, 695, 732, 697, 730, 699, 728, 701, 726, 703, 724,
705, 722, 707, 720, 709, 718, 711, 716, 713, 714, 715, 712, 717, 710, 719, 708, 721,
706, 723, 704, 725, 702, 727, 700, 729, 698, 731, 696, 733, 694, 735, 692, 737, 690,
739, 688, 741, 686, 743, 684, 745, 682, 747, 680, 749, 678, 751, 676, 753, 674, 755,
672, 757, 670, 759, 848, 761, 846, 763, 844, 765, 842, 767, 840, 769, 838, 771, 836,
773, 834, 775, 832, 777, 830, 779, 828, 781, 826, 783, 824, 785, 822, 787, 820, 789,
818, 791, 816, 793, 814, 795, 812, 797, 810, 799, 808, 801, 806, 803, 804, 805, 802,
807, 800, 809, 798, 811, 796, 813, 794, 815, 792, 817, 790, 819, 788, 821, 786, 823,
784, 825, 782, 827, 780, 829, 778, 831, 776, 833, 774, 835, 772, 837, 770, 839, 768,
841, 766, 843, 764, 845, 762, 847, 760, 849, 872, 851, 870, 853, 868, 855, 866, 857,
864, 859, 862, 861, 860, 863, 858, 865, 856, 867, 854, 869, 852, 871, 850, 873, 998,
875, 996, 877, 994, 879, 992, 881, 990, 883, 988, 885, 986, 887, 984, 889, 982, 891,
980, 893, 978, 895, 976, 897, 974, 899, 972, 901, 970, 903, 968, 905, 966, 907, 964,
909, 962, 911, 960, 913, 958, 915, 956, 917, 954, 919, 952, 921, 950, 923, 948, 925,
946, 927, 944, 929, 942, 931, 940, 933, 938, 935, 936, 937, 934, 939, 932, 941, 930,
943, 928, 945, 926, 947, 924, 949, 922, 951, 920, 953, 918, 955, 916, 957, 914, 959,
912, 961, 910, 963, 908, 965, 906, 967, 904, 969, 902, 971, 900, 973, 898, 975, 896,
977, 894, 979, 892, 981, 890, 983, 888, 985, 886, 987, 884, 989, 882, 991, 880, 993,
878, 995, 876, 997, 874, 999,
]
.into_iter()
.skip(1)
.step_by(2)
.copied()
.take_while(|v| *v + 300 < n)
.collect();
for u in &mut used {
*u = false;
}
for e in &even {
used[*e] = true;
}
assert!(rec(n, &mut used, &mut even));
}
(1usize..)
.step_by(2)
.zip(even.into_iter())
.map(|(a, b)| vec![a, b])
.flatten()
.chain(std::iter::once(n))
.take(n)
.collect()
// let mut rng = rand::thread_rng();
// // let sum = n * (n - 1);
// // // Find two primes a and b such that a*(n//2)
// 'retrier: loop {
// let mut used = vec![false; n];
// let mut res = Vec::new();
// // Insert first
// let start: usize = 0; //Uniform::from(0..n).sample(&mut rng);
// res.push(start + 1);
// used[start] = true;
// 'sampler: for i in 1..n {
// let start: usize = Uniform::from(0..n).sample(&mut rng);
// for i in (start..n).chain(0..start) {
// if !used[i] && is_prime(1 + i + res.last().unwrap()) {
// res.push(i + 1);
// used[i] = true;
// continue 'sampler;
// }
// }
// continue 'retrier;
// }
// break res;
// }
}
fn main() {
let stdin = std::io::stdin();
let stdin = stdin.lock();
let mut lines = stdin.lines();
let n = usize::from_str(&lines.next().unwrap().unwrap()).unwrap();
let mut res = solve(n).into_iter();
print!("{}", res.next().unwrap());
for r in res {
print!(" {}", r);
}
println!();
}
#[cfg(test)]
mod tests {
use super::*;
fn is_prime(p: usize) -> bool {
if p == 2 {
return true;
}
if p == 1 || p % 2 == 0 {
return false;
}
for i in (3..).step_by(2) {
if i * i > p {
return true;
}
if p % i == 0 {
return false;
}
}
unreachable!();
}
fn is_valid(list: Vec<usize>) -> bool {
for (l, r) in list.iter().zip(list.iter().skip(1)) {
if !is_prime(l + r) {
println!("{} + {} = {} is not prime", l, r, l + r);
return false;
}
}
let mut list = list;
list.sort();
list == (1..=list.len()).collect::<Vec<usize>>()
}
#[test]
fn test_is_prime() {
assert_eq!(is_prime(1), false, "1");
assert_eq!(is_prime(2), true, "2");
assert_eq!(is_prime(3), true, "3");
assert_eq!(is_prime(4), false, "4");
assert_eq!(is_prime(5), true, "5");
assert_eq!(is_prime(6), false, "6");
assert_eq!(is_prime(7), true, "7");
assert_eq!(is_prime(50), false, "50");
assert_eq!(is_prime(53), true, "49");
assert_eq!(is_prime(997), true, "997");
assert_eq!(is_prime(1000), false, "1000");
}
#[test]
fn test_small() {
for i in 2..=10 {
assert!(is_valid(solve(i)));
}
}
#[test]
fn test_medium() {
use std::time::Instant;
for i in 11..=100 {
let start = Instant::now();
let result = solve(i);
let stop = Instant::now();
assert!(is_valid(result.clone()), "{:?}", result);
let time = (stop - start).as_secs_f64();
assert!(time < 1.0, "Input {} took {}", i, time);
}
}
#[test]
fn test_large() {
use std::time::Instant;
for i in 101..=1000 {
let start = Instant::now();
let result = solve(i);
let stop = Instant::now();
assert!(is_valid(result.clone()), "{:?}", result);
let time = (stop - start).as_secs_f64();
assert!(time < 1.0, "Input {} took {}", i, time);
}
}
}
