Coloring Array with Prime Multiplication Constraint

You are given an array \(A = [a_1, a_2, \dots, a_n]\) consisting of \(n\) positive integers. Your task is to assign one of two colors to each element of the array such that for any two elements of the same color, say \(x\) and \(y\), the following condition is never satisfied:

• \(x = p \times y\), where \(p\) is a prime number.

It is guaranteed that for the given input, a valid coloring exists.

Note: It is allowed for two equal numbers to have the same color since the ratio would be 1 and 1 is not a prime.

inputFormat

The first line contains an integer \(n\) representing the number of elements in the array. The second line contains \(n\) space-separated positive integers \(a_1, a_2, \dots, a_n\).

outputFormat

Output a single line containing \(n\) integers (each either 0 or 1) separated by a space. The \(i\)th integer denotes the color assigned to \(a_i\). Any valid coloring that satisfies the given condition is acceptable.

sample

3
2 6 3

0 1 0