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].
import java.util.*;
import java.io.*;

public class ProbE {
	public static void main(String[] args) {
		ProbE sol = new ProbE();
		sol.start();
	}

	StringBuffer printstr;

	public void print(Object o){ System.out.print(o); }
	public void println(Object o) { System.out.println(o); }

	public void bufp(Object o){ printstr.append(o); }
	public void bufpl(Object o){ printstr.append(o).append('\n'); }
	public void bufpl() { printstr.append('\n'); }
	public void bufp(char[] c, int offset, int len){ printstr.append(c, offset, len); }
	public void bufpl(char[] c, int offset, int len){ printstr.append(c, offset, len).append('\n'); }

	public void start(){
		submit();
	}
	
	public void submit(){
	try{
		printstr = new StringBuffer();
		Scanner scan = new Scanner(System.in);
		BufferedReader rdr = new BufferedReader(new InputStreamReader(System.in));
		String[] s = rdr.readLine().split(" ");
		int n = Integer.parseInt(s[0]);
		int m = Integer.parseInt(s[1]);
		int[] forbidden = new int[n];
		if(n!=0){
			s = rdr.readLine().split(" ");
			for(int i=0;i<n;i++) forbidden[i] = Integer.parseInt(s[i]);
		}
		scan.close();
		
		vulnerableKerbals(n, m, forbidden);
		System.out.println(printstr);
		System.out.flush();
	}
	catch(Exception e){e.printStackTrace();}
	}
	
	class NumNode{
		int val;
		HashSet<NumNode> directMultiples;
		HashSet<NumNode> directDivisors;
		int size; //how many numbers in [0..m-1] have gcd with m equal to val
		int maxChainLength;
		NumNode maxChainNode;
		HashSet<Integer> forbidden;
		
		public NumNode(int k){
//			println("Constructing node "+k);
			val = k;
			directMultiples = new HashSet();
			directDivisors = new HashSet();
			maxChainLength = -1;
			maxChainNode = null;
			forbidden = new HashSet();
			size = phi(mvalue / val);
//			println("Node "+k+" size="+size+"= phi of "+(mvalue/val));
			for(Integer i : primefactors){
				if(i>k) break;
				if(k%i!=0) continue;
				int j = k/i;
				NumNode child = nodemap.get(j);
				if(child==null){
					child = new NumNode(j);
					nodemap.put(j, child);
				}
				directDivisors.add(child);
				child.directMultiples.add(this);
			}
		}
		
		public void findMax(){
			for(NumNode parent : directMultiples){
				if(parent.maxChainLength==-1) parent.findMax();
				int tmp = parent.maxChainLength + size - forbidden.size();
				if(tmp>maxChainLength){
					maxChainLength = tmp;
					maxChainNode = parent;
				}
			}
//			println("Node="+val);
//			print("  DirectDivisors: ");
//			for(NumNode node : directDivisors) print(node.val+" ");
//			println(" ");
//			print("  DirectMultiples: ");
//			for(NumNode node : directMultiples) print(node.val+" ");
//			println(" ");
//			print("  Length="+maxChainLength+" next=");
//			if(maxChainNode==null) println("null");
//			else println(maxChainNode.val);
		}
		
		public LinkedList<Integer> getCurrentLevelList(){
			LinkedList<Integer> ret = new LinkedList();
			int p = mvalue / val;
			for(int i=0;i<p;i++) if(gcd(i,p)==1){
				if(forbidden.contains(i*val)) continue;
				ret.add(i*val);
			}
			return ret;
		}
		
		
	}
	
	int mvalue;
	HashMap<Integer, NumNode> nodemap;
	LinkedList<Integer> primefactors;
	
	public void vulnerableKerbals(int n, int m, int[] forbvals){
		mvalue = m;
		nodemap = new HashMap();
		primefactors = new LinkedList();
		setPrimeFactors(m);
		nodemap.put(m, new NumNode(m));
		for(int forbval : forbvals){
			int k = gcd(forbval, m);
			NumNode node = nodemap.get(k);
			node.forbidden.add(forbval);
		}
		NumNode first = nodemap.get(1);
		NumNode last = nodemap.get(m);
		last.maxChainNode = null;
		last.maxChainLength = last.size - last.forbidden.size();
		first.findMax();
		bufpl(first.maxChainLength);
		if(first.maxChainLength==0) return;
		LinkedList<Integer> prod = new LinkedList();
		for(NumNode cur = first; cur!=null; cur = cur.maxChainNode){
			LinkedList<Integer> next = cur.getCurrentLevelList();
			for(Integer i : next) prod.add(i);
		}
		int val = 1;
		for(Integer next : prod){
			int cur = divideFactor(next,val);
			val = next;
			bufp(cur+" ");
		}
	}
	
	public int divideFactor(int prod, int f){
		//return g so that f * g = prod mod m
		int g = gcd(mvalue, gcd(prod, f));
		int m  = mvalue / g;
		prod /= g;
		f /= g;
		g = gcd(prod, f);
		prod /= g;
		f /= g;
		
		long ret = (long) prod;
		ret = ret * invert(f, m);
		ret = ret % m;
		return (int) ret;
	}
	
	public int invert(int a, int m){
		int ret = bezout_recursive(a, m)[0];
		ret %= m;
		ret = (ret+m) % m;
		return ret;
	}
	
	public int[] bezout_recursive(int x, int y){
		//return int[] {a, b, g} so that a*x + b*y = g = gcd(x,y) >= 0.
		if(x<0) x = -x;
		if(y<0) y = -y;
		if(y==0) return new int[] {1, 0, x};
		if(x<y){
			int[] ret = bezout_recursive(y, x);
			return new int[] {ret[1], ret[0], ret[2]};
		}
		
		int q = x / y;
		int r = x % y;
		int[] ret = bezout_recursive(y, r);
		//now y  * ret[0] + (x-q*y) * ret[1] = ret[2]
		//so ret[1] * x + (ret[0] - q * ret[1]) * y = ret[2]
		return new int[] { ret[1], ret[0] - q * ret[1], ret[2]};
	}
	
	//add all prime factors of m into HashSet primefactors
	public void setPrimeFactors(int m){
		boolean[] mark = new boolean[m+1];
		Arrays.fill(mark, true);
		for(int i=2;i<=m;i++){
			if(!mark[i]) continue;
			for(int j=i*2;j<=m;j+=i) mark[j] = false;
		}
		for(int i=2;i<=m;i++) if(mark[i] && m%i==0) {
			primefactors.add(i);
//			println(i);
		}
	}
	
	public int gcd(int x, int y){
		if(x<y){
			int z = y;
			y = x;
			x = z;
		}
		while(y!=0){
			int z = x%y;
			x = y;
			y = z;
		}
		return x;
	}
	
	public int phi(int n){
		//compute the Euler phi value of n, where n is a divisor of m
		int ret = 1;
		for(Integer i : primefactors){
			if(i>n) break;
			if(n%i!=0) continue;
			while(n%i==0){
				n /= i;
				ret *= i;
			}
			ret = ret / i;
			ret = ret * (i-1);
		}
//		println("phi value of "+m+" is "+ret);
		return ret;
	}
	
}