Two Out of Three Solution codeforces

You are given an array $a_{1}, a_{2}, \dots, a_{n}$ . You need to find an array $b_{1}, b_{2}, \dots, b_{n}$ consisting of numbers $1$ , $2$ , $3$ such that exactly two out of the following three conditions are satisfied:

There exist indices $1 \leq i, j \leq n$ such that $a_{i} = a_{j}$ , $b_{i} = 1$ , $b_{j} = 2$ .
There exist indices $1 \leq i, j \leq n$ such that $a_{i} = a_{j}$ , $b_{i} = 1$ , $b_{j} = 3$ .
There exist indices $1 \leq i, j \leq n$ such that $a_{i} = a_{j}$ , $b_{i} = 2$ , $b_{j} = 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$ $(1 \leq t \leq 500)$ — the number of test cases. Each test case is described as follows.

The first line of each test case contains an integer $n$ $(1 \leq n \leq 100)$ — the length of the array $a$ .

The second line of each test case contains $n$ integers $a_{1}, a_{2}, \dots, a_{n}$ $(1 \leq a_{i} \leq 100)$ — the elements of the array $a$ .

Output

For each test case, print -1 if there is no solution. Otherwise, print $b_{1}, b_{2}, \dots, b_{n}$ — an array consisting of numbers $1$ , $2$ , $3$ that satisfies exactly two out of three conditions. If there are multiple possible answers, you can print any of them.

Example

input

Copy

1 2 3 2 2 3

7 7 7 7 7 7 7

1 1 2 2

1 2 3 4 5 6 7

2 3 3 3 2

1 2 1

1 1 1 7 7 7 9 9 9

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

B. Two Out of Three

Leave a Comment Cancel reply