B. Два из трёх
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив $$$a_1, a_2, \ldots, a_n$$$. Вам нужно найти такой массив $$$b_1, b_2, \ldots, b_n$$$, который состоит из чисел $$$1$$$, $$$2$$$, $$$3$$$, и для него выполняются ровно два из следующих трёх условий:

  1. Существуют такие индексы $$$1 \leq i, j \leq n$$$, для которых $$$a_i = a_j$$$, $$$b_i = 1$$$, $$$b_j = 2$$$.
  2. Существуют такие индексы $$$1 \leq i, j \leq n$$$, для которых $$$a_i = a_j$$$, $$$b_i = 1$$$, $$$b_j = 3$$$.
  3. Существуют такие индексы $$$1 \leq i, j \leq n$$$, для которых $$$a_i = a_j$$$, $$$b_i = 2$$$, $$$b_j = 3$$$.

Если подходящего массива не существует, вы должны сообщить об этом.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит целое число $$$t$$$ $$$(1 \leq t \leq 500)$$$ — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит целое число $$$n$$$ $$$(1 \leq n \leq 100)$$$ — длину массива $$$a$$$.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ $$$(1 \leq a_i \leq 100)$$$ — элементы массива $$$a$$$.

Выходные данные

Для каждого набора входных данных выведите -1, если ответа не существует. Иначе выведите $$$b_1, b_2, \ldots, b_n$$$ — массив, состоящий из чисел $$$1$$$, $$$2$$$, $$$3$$$ и подходящий под ровно два условия из трёх перечисленных. Если ответов несколько, вы можете вывести любой из них.

Пример
Входные данные
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
Выходные данные
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 = [1, 2, 3, 1, 1, 1]$$$ подходит под условие $$$1$$$ так как при $$$i = 4$$$, $$$j = 2$$$: $$$a_i = a_j$$$, $$$b_i = 1$$$, $$$b_j = 2$$$. Подходит под условие $$$2$$$ так как при $$$i = 6$$$, $$$j = 3$$$: $$$a_i = a_j$$$, $$$b_i = 1$$$, $$$b_j = 3$$$, и не подходит под условие $$$3$$$. Итого выполнено ровно два условия из трёх.