P11124 [ROIR 2024] 数组划分 (Day 2)

翻译自 [ROIR 2024 D2T1](https://neerc.ifmo.ru/school/archive/2023-2024/ru-olymp-regional-2024-day2.pdf)。

给定一个数组 $A = [a_1, a_2, \dots, a_n]$，其中包含 $n$ 个正整数。 需要将数组元素涂成两种颜色，使得任意两个同一颜色的元素 $x$ 和 $y$ 不满足以下条件： - $x=p\times y$，其中 $p$ 是一个素数。 保证存在这样的涂色方案。

第一行包含一个整数 $n$（$1 \leq n \leq 100000$），表示数组的元素个数。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq 10^6$），即数组中的元素。

输出数组的划分方案。具体地，输出一行 $n$ 个整数，如果第 $i$ 个数字为 $1$，表示第 $i$ 个元素应涂成第一种颜色；如果为 $2$，则表示第 $i$ 个元素应涂成第二种颜色。 如果存在多个合适的划分方案，可以输出其中任何一个。

| 子任务 | 分值 | 特殊性质 | | :----------: | :----------: | :----------: | | $0$ | $0$ | 同样例 | | $1$ | $9$ | $a_i\le2$ | | $2$ | $19$ | $a_i=p^k$，其中 $p$ 是素数 | | $3$ | $12$ | $a_i\le3$ | | $4$ | $13$ | $a_i\le4$ | | $5$ | $21$ | $n\le10$ | | $6$ | $26$ | 无 | 对于 $100\%$ 的数据，$1 \leq n \leq 100000$，$1 \leq a_i \leq 10^6$。