You are given an integer m, and a list of n distinct integers between 0 and m - 1.

You would like to construct a sequence satisfying the properties:

  * Each element is an integer between 0 and m - 1, inclusive. 
  * All prefix products of the sequence modulo m are distinct. 
  * No prefix product modulo m appears as an element of the input list. 
  * The length of the sequence is maximized. 



Construct any sequence satisfying the properties above.

Input

The first line of input contains two integers n and m (0 ≤ n < m ≤ 200 000) — the number of forbidden prefix products and the modulus.

If n is non-zero, the next line of input contains n distinct integers between 0 and m - 1, the forbidden prefix products. If n is zero, this line doesn't exist.

Output

On the first line, print the number k, denoting the length of your sequence.

On the second line, print k space separated integers, denoting your sequence.

Examples

Input

0 5


Output

5
1 2 4 3 0


Input

3 10
2 9 1


Output

6
3 9 2 9 8 0

Note

For the first case, the prefix products of this sequence modulo m are [1, 2, 3, 4, 0].

For the second case, the prefix products of this sequence modulo m are [3, 7, 4, 6, 8, 0].
#include <bits/stdc++.h>
using std::map;
using std::pair;
using std::set;
using std::vector;
using Remainder = int64_t;
int64_t Gcd(int64_t a, int64_t b);
pair<int64_t, int64_t> LrpGcd(int64_t a, int64_t b);
int64_t DivideMod(int64_t a, int64_t b, int64_t mod);
pair<int64_t, set<Remainder>> ReadInput(std::istream& in_stream = std::cin);
void WriteAnswer(const vector<Remainder>& answer,
                 std::ostream& out_stream = std::cout);
vector<int64_t> Solve(int64_t modulo, const set<Remainder>& ignore);
int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);
  auto input = ReadInput();
  auto result = Solve(input.first, input.second);
  WriteAnswer(result);
  return 0;
}
struct Primes {
 private:
  vector<int64_t> primes;

 public:
  Primes() : primes{2, 3, 5, 7, 11, 13} {}
  bool operator()(int64_t prime);
};
Primes is_prime;
using Divisor = int64_t;
vector<Divisor> BestWay(int64_t modulo, const set<Remainder>& ignore_);
vector<int64_t> Solve(int64_t modulo, const set<Remainder>& ignore_) {
  set<Remainder> ignore = ignore_;
  vector<Remainder> result;
  Remainder current = 1;
  auto best_way = BestWay(modulo, ignore_);
  for (auto gcd : best_way) {
    for (Remainder start = gcd; start <= modulo; start += gcd) {
      if (Gcd(start, modulo) == gcd &&
          ignore.find(start % modulo) == ignore.end()) {
        result.push_back(DivideMod(start, current, modulo));
        ignore.insert(start);
        current = start;
      }
    }
  }
  return result;
}
map<Divisor, size_t> ByPrimes(int64_t modulo);
class Dynamic {
 private:
  int64_t modulo;
  vector<Divisor> primes;
  map<Divisor, pair<size_t, Divisor>> next;
  map<Divisor, size_t> values;

 public:
  Dynamic(const map<Divisor, size_t>& values_, const vector<Divisor>& primes,
          int64_t modulo)
      : values(values_), primes(primes), modulo(modulo) {}
  pair<size_t, Divisor> Next(Divisor current);
};
void Fill(size_t pos, Divisor current, const vector<Divisor>& primes,
          const vector<size_t>& degrees, map<Divisor, size_t>* values,
          int64_t modulo, const set<Remainder>& ignore);
vector<Divisor> BestWay(int64_t modulo, const set<Remainder>& ignore_) {
  map<Divisor, size_t> prime_degrees = ByPrimes(modulo);
  vector<Divisor> primes;
  vector<size_t> degrees;
  for (auto prime_degree : prime_degrees) {
    primes.push_back(prime_degree.first);
    degrees.push_back(prime_degree.second);
  }
  map<Divisor, size_t> values;
  Fill(0, 1, primes, degrees, &values, modulo, ignore_);
  Dynamic next(values, primes, modulo);
  vector<Divisor> answer{1};
  while (answer.back() != 0 && answer.back() != modulo) {
    answer.push_back(next.Next(answer.back()).second);
  }
  return answer;
}
pair<size_t, Divisor> Dynamic::Next(Divisor current) {
  if (next.find(current) != next.end()) {
    return next[current];
  } else {
    pair<size_t, Divisor> best_;
    for (auto prime : primes) {
      if (modulo % (current * prime) == 0) {
        auto potential = Next(current * prime);
        if (best_.first < potential.first) {
          best_.first = potential.first;
          best_.second = current * prime;
        }
      }
    }
    best_.first += values[current];
    next[current] = best_;
    return best_;
  }
}
void Fill(size_t pos, Divisor current, const vector<Divisor>& primes,
          const vector<size_t>& degrees, map<Divisor, size_t>* values,
          int64_t modulo, const set<Remainder>& ignore) {
  if (pos < primes.size()) {
    for (size_t degree = 0; degree <= degrees[pos];
         ++degree, current *= primes[pos]) {
      Fill(pos + 1, current, primes, degrees, values, modulo, ignore);
    }
  } else {
    for (Divisor divide = current; divide <= modulo; divide += current) {
      if (Gcd(modulo, divide) == current) {
        if (ignore.find(divide) == ignore.end()) {
          ++(*values)[current];
        }
      }
    }
  }
}
map<Divisor, size_t> ByPrimes(int64_t modulo) {
  map<Divisor, size_t> degree;
  for (Divisor divisor = 2; divisor * divisor <= modulo; ++divisor) {
    for (; modulo % divisor == 0; modulo /= divisor) {
      ++degree[divisor];
    }
  }
  if (modulo != 1) {
    ++degree[modulo];
  }
  return degree;
}
bool Primes::operator()(int64_t prime) {
  if (prime <= primes.back()) {
    return *std::lower_bound(primes.begin(), primes.end(), prime) == prime;
  } else if (prime <= primes.back() * primes.back()) {
    for (int64_t divisor : primes) {
      if (prime % divisor == 0) {
        return 0;
      }
    }
    return 1;
  } else {
    for (int64_t pre_prime = primes.back() + 1;
         primes.back() * primes.back() <= prime; ++pre_prime) {
      if (this->operator()(pre_prime)) {
        primes.push_back(pre_prime);
      }
    }
    return this->operator()(prime);
  }
}
int64_t DivideMod(int64_t a, int64_t b, int64_t mod) {
  auto gcd = Gcd(b, mod);
  a /= gcd;
  b /= gcd;
  mod /= gcd;
  auto lrp_gcd = LrpGcd(b, mod);
  return (a * mod + lrp_gcd.first * a) % mod;
}
int64_t Gcd(int64_t a, int64_t b) { return (b) ? Gcd(b, a % b) : a; }
pair<int64_t, int64_t> LrpGcd(int64_t a, int64_t b) {
  if (b == 0) {
    return {1, 0};
  }
  auto prev = LrpGcd(b, a % b);
  return {prev.second, prev.first - (a / b) * prev.second};
}
void WriteAnswer(const vector<Remainder>& answer, std::ostream& out_stream) {
  out_stream << answer.size() << std::endl;
  for (auto remainder : answer) {
    out_stream << remainder << ' ';
  }
}
pair<int64_t, set<Remainder>> ReadInput(std::istream& in_stream) {
  int64_t ignore_size, modulo;
  in_stream >> ignore_size >> modulo;
  set<Remainder> ignore;
  for (size_t ignore_num = 0; ignore_num < ignore_size; ++ignore_num) {
    Remainder ignore_;
    in_stream >> ignore_;
    ignore.insert(ignore_ % modulo);
  }
  return {modulo, ignore};
}
