题目描述

译自 ROI Regional 2024 Day2 T1. Разбиение массива

给定一个包含 $n$ 个自然数的数组 $A = [a_1, a_2, \ldots, a_n]$。

需要将数组元素划分为两种颜色，使得不存在两个同色的元素 $x$ 和 $y$ 满足 $x$ 可以整除 $y$ 且 $\frac{x}{y} = p$，其中 $p$ 是一个质数。保证这样的划分是存在的。

输入格式

第一行包含一个整数 $n$ $(1 \le n \le 10^5)$，表示数组的元素数量。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ $(1 \le a_i \le 10^6)$，表示数组的元素。

输出格式

输出数组划分为两种颜色的描述。

输出 $n$ 个整数，如果第 $i$ 个元素 $a_i$ 被划分为第一种颜色，则输出 $1$；如果被划分为第二种颜色，则输出 $2$。

如果存在多种合适的划分方案，可以输出任意一种。

4
1 2 3 4

2 1 1 2

在第一个样例中，第一种颜色的元素有 $2$ 和 $3$，第二种颜色的元素有 $1$ 和 $4$。第一种颜色的元素之间不能整除。$4$ 可以整除 $1$，但它们的比值不是质数。

1
20

1

数据范围与提示

详细子任务附加限制及分值如下表所示。