# Two Out of Three Solution codeforces

## B. Two Out of Three

time limit per test

3 seconds

memory limit per test

512 megabytes

input

standard input

output

standard output

You are given an array a1,a2,,an�1,�2,…,��. You need to find an array b1,b2,,bn�1,�2,…,�� consisting of numbers 112233 such that exactly two out of the following three conditions are satisfied:

1. There exist indices 1i,jn1≤�,�≤� such that ai=aj��=��bi=1��=1bj=2��=2.
2. There exist indices 1i,jn1≤�,�≤� such that ai=aj��=��bi=1��=1bj=3��=3.
3. There exist indices 1i,jn1≤�,�≤� such that ai=aj��=��bi=2��=2bj=3��=3.

If such an array does not exist, you should report it.

Input

Each test contains multiple test cases. The first line contains a single integer t (1t500)(1≤�≤500) — the number of test cases. Each test case is described as follows.

The first line of each test case contains an integer n (1n100)(1≤�≤100) — the length of the array a.

The second line of each test case contains n integers a1,a2,,an�1,�2,…,�� (1ai100)(1≤��≤100) — the elements of the array a.

Output

For each test case, print -1 if there is no solution. Otherwise, print b1,b2,,bn�1,�2,…,�� — an array consisting of numbers 112233 that satisfies exactly two out of three conditions. If there are multiple possible answers, you can print any of them.

Example
input

Copy
9
6
1 2 3 2 2 3
7
7 7 7 7 7 7 7
4
1 1 2 2
7
1 2 3 4 5 6 7
5
2 3 3 3 2
3
1 2 1
9
1 1 1 7 7 7 9 9 9
1
1
18
93 84 50 21 88 52 16 50 63 1 30 85 29 67 63 58 37 69
output

Copy
1 2 3 1 1 1
-1
3 2 2 1
-1
2 1 2 1 3
-1
1 1 2 2 1 2 2 3 3
-1
3 2 1 3 3 3 3 2 2 1 1 2 3 1 3 1 1 2