description: Let's call a set of positive integers a_1, a_2, ..., a_k quadratic if the product of the factorials of its elements is a square of an integer, i. e. ∏_{i=1}^{k} a_i! = m^2, for some integer m.
  
  You are given a positive integer n.
  
  Your task is to find a quadratic subset of a set 1, 2, ..., n of maximum size. If there are multiple answers, print any of them.
  
  Input
  
  A single line contains a single integer n (1 ≤ n ≤ 10^6).
  
  Output
  
  In the first line, print a single integer — the size of the maximum subset. In the second line, print the subset itself in an arbitrary order.
  
  Examples
  
  Input
  
  
  1
  
  
  Output
  
  
  1
  1 
  
  
  Input
  
  
  4
  
  
  Output
  
  
  3
  1 3 4 
  
  
  Input
  
  
  7
  
  
  Output
  
  
  4
  1 4 5 6 
  
  
  Input
  
  
  9
  
  
  Output
  
  
  7
  1 2 4 5 6 7 9 
solution: #include <bits/stdc++.h>
  using namespace std;
  mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
  inline unsigned long long my_rand() { return rnd() + rnd(); }
  int prime[100005], tot;
  bool not_prime[1000005];
  unsigned long long w[1000005], sum[1000005];
  bool banned[1000005];
  void sieve(int n) {
    not_prime[1] = true;
    for (int i = 2; i <= n; ++i) {
      if (!not_prime[i]) {
        prime[++tot] = i;
      }
      for (int j = 1; j <= tot && i * prime[j] <= n; ++j) {
        not_prime[i * prime[j]] = true;
        if (i % prime[j] == 0) {
          break;
        }
      }
    }
    for (int i = 1; i <= tot; ++i) {
      int x = prime[i];
      unsigned long long cur = my_rand();
      for (int j = x; j <= n; j += x) {
        bool f = true;
        for (int y = j / x; y % x == 0; y /= x) {
          f ^= 1;
        }
        if (f) {
          w[j] ^= cur;
        }
      }
    }
    for (int i = 1; i <= n; ++i) {
      sum[i] = sum[i - 1] ^ w[i];
    }
  }
  void output() {}
  int main() {
    sieve(1000000);
    int n;
    cin >> n;
    map<unsigned long long, int> rev;
    unsigned long long all = 0;
    auto output = [&]() {
      vector<int> p;
      for (int i = 1; i <= n; ++i) {
        if (!banned[i]) {
          p.emplace_back(i);
        }
      }
      cout << p.size() << "\n";
      for (auto x : p) {
        cout << x << " ";
      }
      exit(0);
    };
    for (int i = 1; i <= n; ++i) {
      rev[sum[i]] = i;
      all ^= sum[i];
    }
    if (!all) {
      output();
    }
    if (rev.count(all)) {
      banned[rev[all]] = true;
      output();
    }
    for (int i = 1; i <= n; ++i) {
      unsigned long long x = sum[i];
      if (rev.count(all ^ x)) {
        int j = rev[all ^ x];
        banned[i] = banned[j] = true;
        output();
      }
    }
    assert(n & 1);
    banned[n] = banned[(n - 1) / 2] = banned[2] = true;
    output();
    return 0;
  }
  