F. Kinan The Bank Robber
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Kinan wanted to attend the World Cup so badly, but sadly he did not have enough money to make it there, so he went robbing banks around the city with the help of his friend Rajaee.

One day while they were doing their job in some bank, they found a precious array $$$a_1, a_2, \dots, a_n$$$ of positive integer numbers and each one of them wanted to take that array for himself.

They came up with the idea of splitting the array elements into exactly two groups, one for Kinan(group $$$1$$$) and one for Rajaee(group $$$2$$$), according to some conditions to guarantee justice. The conditions are described in the following:

  • Each element should belong to exactly one group.
  • One of the two groups can be empty.
  • Every pair of elements belonging to the same group must be coprime.

Two positive integers $$$x, y$$$ are coprime if their greatest common divisor is $$$1$$$, $$$\gcd(x,y) = 1$$$.

You are asked to predict a way Kinan and Rajaee can split the array according to these rules, or state that they cannot split it. If there are many ways to split the array, printing any valid way is acceptable.

Input

The first line contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$), the number of elements in the array.

The second line contains $$$n$$$ positive integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^7$$$), the elements of the array, separated by spaces.

Output

If a valid split exists, print a single line containing $$$n$$$ space-separated integers. The $$$i$$$-th integer should be $$$1$$$ if element $$$a_i$$$ is assigned to group $$$1$$$, and $$$2$$$ if element $$$a_i$$$ is assigned to group $$$2$$$.

If multiple valid splits exist, you may print any one.

If it is impossible to split the array according to the conditions, print a single line containing only the integer $$$-1$$$.

Examples
Input
5
10 30 21 7 1
Output
1 2 1 2 1
Input
6
1 30 12 25 11 13
Output
1 1 2 2 1 1
Input
3
2 2 2
Output
-1