Problem Description

Given a sequence \( a \) of length \( n \) containing only positive integers, where \( n \) is guaranteed to be even. You need to rearrange \( a \) such that for every even-length prefix of \( a \), the number of distinct digits is even, or determine that such a rearrangement does not exist.

If there are multiple valid rearrangements, output any one of them.

Input Format

The first line contains a positive integer \( n \), which is guaranteed to be even.

The second line contains \( n \) positive integers, describing the sequence \( a \).

Output Format

Output \(-1\) if no solution exists; otherwise, output a single line containing \( n \) integers, describing the rearranged sequence \( a \).

This problem uses a custom validator to check if your answer is correct. If there are multiple valid rearrangements, output any one of them.

Sample Input and Output

Sample Input #1

6
2 3 3 4 1 1

Sample Output #1

1 3 3 1 2 4

Sample Input #2

2
1 1

Sample Output #2

-1

Notes

[Sample Explanation 1]

The sets \(\{1,3\}\), \(\{1,3,3,1\}\), and \(\{1,3,3,1,2,4\}\) all have an even number of distinct digits.

[Data Range]

This problem uses subtask-based testing.

For \(100\%\) of the data, \(2 \le n \le 10^5\), \(1 \le a_i \le n\), and \( n \) is guaranteed to be even.

见题面 Input 部分

见题面 Output 部分