Given a set of *n* natural numbers,
choose any subset *S*
such that ∏_{x ∈ S} ≡ 1 (mod *n* ).

**Input**

Input consists of several cases.
Every case begins with *n*,
followed by *n* different numbers, all between 1 and 10^{9}.
Assume 2 ≤ *n* ≤ 10^{5}.

It is easy to see that no number *x* where gcd(*x*, *n*) ≠ 1
could ever be part of any solution.
Consequently, every given *x* is such that gcd(*x*, *n*) = 1.

**Output**

Print one line for every case,
with a non-empty subset of the given numbers
such that the product of its elements is congruent with 1 modulo *n*.
Each number can be used at most once.
Print the numbers in any order, and separated by one space.
If there are several solutions, print any of them.
If there is no solution, print “`Maths are difficult`”.

Public test cases

**Input**

5 9 8 2 6 4 5 9 8 2 6 4 2 1 3 4 10000003 10000007 10000011 10000015 5 23 18 3 8 13

**Output**

8 2 9 8 6 4 2 3 10000003 10000007 23 18 3 8

Information

- Author
- Salvador Roura
- Language
- English
- Official solutions
- C++
- User solutions
- C++
- Event
- Desè Concurs de Programació de la UPC - Final
- Date
- 2012-09-15