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].

Source: codeforces | Difficulty: HARD
Tags: Graph algorithms

Constructive algorithms

Number theory

Dynamic programming

Mathematics


Solutions:
maxn = 200500
g = [[] for i in range(maxn)]
dp = [0 for i in range(maxn)]
ban = [0 for i in range(maxn)]
nxt = [0 for i in range(maxn)]
m = 0

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def exgcd(a, b):
	if b == 0:
		x = 1
		y = 0
		return (a, x, y)
	(ret, x, y) = exgcd(b, a % b)
	tmp = x
	x = y
	y = tmp - int(a / b) * y
	return (ret, x, y)

def f(a, b):
	(r1, x, y) = exgcd(a, m)
	if b % r1 != 0:
		return -1
	x = (x + m) % m * int(b / r1) % m
	return x

def dfs(p):
	if dp[p] != 0:
		return
	res = 0
	for i in range(p * 2, m, p):
		if len(g[i]) > 0:
			dfs(i)
		if dp[i] > res:
			res = dp[i]
			nxt[p] = i
	if len(g[p]) > 0:
		res += len(g[p])
	dp[p] = res
(a, b) = input().split(' ')
n = int(a)
m = int(b)
if n > 0:
	lista = input().split(' ')
for i in range(1, n + 1):
	x = int(lista[i - 1])
	ban[x] = 1
for i in range(1, m):
	if ban[i] == 0:
		d = gcd(i, m)
		g[d].append(i)
dfs(1)
ban0 = 0
if ban[0] == ban0:
	ban0 = 1
print(dp[1] + ban0)
u = 1
x = 1
sec = ''
while u != 0:
	for i in range(0, len(g[u])):
		v = g[u][i]
		print(str(f(x, v)) + ' ', end=' ')
		x = v
	u = nxt[u]
if ban0 == 1:
	print('0')


import math

def gcdExtended(a, b):
	if a == 0:
		return (b, 0, 1)
	(gcd, x1, y1) = gcdExtended(b % a, a)
	x = y1 - b // a * x1
	y = x1
	return (gcd, x, y)

def rev_elem(x, m):
	return (gcdExtended(x, m)[1] % m + m) % m
(n, m) = map(int, input().split())
a = []
if n > 0:
	a = [int(i) for i in input().split()]
banned = [False] * (m + 5)
for i in a:
	banned[i] = True
cycle = [[] for i in range(m + 5)]
(d, dp, p) = ([], [], [])
for i in range(m):
	cycle[math.gcd(m, i)].append(i)
cycle = [[i for i in j if not banned[i]] for j in cycle]
d = [i for i in range(1, m + 1) if m % i == 0]
dp = [len(cycle[i]) for i in d]
p = [-1 for i in d]
(ans, lst) = (-1, -1)
for i in range(len(d)):
	if dp[i] > ans:
		(ans, lst) = (dp[i], i)
	for j in range(i + 1, len(d)):
		if d[j] % d[i] != 0 or dp[j] > dp[i] + len(cycle[d[j]]):
			continue
		dp[j] = dp[i] + len(cycle[d[j]])
		p[j] = i
print(ans)
(pos, dpos, pref) = ([], [], [])
cur = lst
while cur != -1:
	dpos.append(d[cur])
	cur = p[cur]
dpos.reverse()
for i in dpos:
	pref += cycle[i]
cur = 1
for i in pref:
	ad = 1
	if math.gcd(i, m) != math.gcd(cur, m):
		ad = cur * math.gcd(i, m) // math.gcd(cur, math.gcd(i, m)) // cur % m
	ncur = cur * ad % m
	ad *= i // math.gcd(ncur, m) * rev_elem(ncur // math.gcd(ncur, m), m // math.gcd(ncur, m))
	ad %= m
	cur = cur * ad % m
	pos.append(ad)
print(*pos)