Codeforces Round 908 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

constructive algorithms

*1000

No tag edit access

The problem statement has recently been changed. View the changes.

×
B. Two Out of Three

time limit per test

3 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputYou are given an array $$$a_1, a_2, \ldots, a_n$$$. You need to find an array $$$b_1, b_2, \ldots, 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, \ldots, 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, \ldots, 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

961 2 3 2 2 377 7 7 7 7 7 741 1 2 271 2 3 4 5 6 752 3 3 3 231 2 191 1 1 7 7 7 9 9 9111893 84 50 21 88 52 16 50 63 1 30 85 29 67 63 58 37 69

Output

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

Note

In the first test case, $$$b = [1, 2, 3, 1, 1, 1]$$$ satisfies condition $$$1$$$ because for $$$i = 4$$$, $$$j = 2$$$: $$$a_i = a_j$$$, $$$b_i = 1$$$, and $$$b_j = 2$$$. It also satisfies condition $$$2$$$ because for $$$i = 6$$$, $$$j = 3$$$: $$$a_i = a_j$$$, $$$b_i = 1$$$, and $$$b_j = 3$$$. However, it does not satisfy condition $$$3$$$. In total, exactly two out of three conditions are satisfied.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/02/2023 06:01:30 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|