题目描述

译自 COCI 2020/2021 Contest #4 T3「Hop」

有 $n$ 片荷叶，每片荷叶有一个数字 $x_i$。

有三只青蛙，在一开始，每只青蛙都可能会在任意一片荷叶上。

每两片荷叶 $(a,b)$ 都必须标记为青蛙 $1$、青蛙 $2$ 和青蛙 $3$。

一只青蛙可以从荷叶 $i$ 跳到荷叶 $j$ ($j>i$) 当且仅当 $(i,j)$ 被标记成这只青蛙且 $x_i \mid x_j$。

您需要为任意两片荷叶进行标记，使得没有出现任意一只青蛙超过三次连跳的情况。

输入格式

第一行一个数字 $n$。

接下来一行 $n$ 个整数 $x_i$。

输出格式

输出 $n-1$ 行，在第 $i$ 行输出 $i$ 个整数，第 $i$ 行第 $j$ 个整数表示 $(j,i+1)$ 的标记情况。

样例 1

输入 8 3 4 6 9 12 18 36 72

text

输出 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1

text

对应标记情况：

三只青蛙被标记成了蓝色，绿色和红色。

被标记成蓝色的青蛙可以跳出这样的路径：$1 \to 4 \to 7 \to 8$，共三步。

没有青蛙可以连续跳超过三步。

样例 2

输入 2 10 101

text

输出 1

text

数据范围与提示

对于所有子任务，保证 $1 \le n \le 10^3$，$1 \le x_i \le 10^{18}$ 且 $x_i$ 严格递增。

子任务编号	约束	分值
1	$n \le 30$	$10/110$
2	无附加限制	$100/110$

如果您的答案会使得一些青蛙连跳 $k$ ($k>3$) 次，并且没有青蛙可以连跳 $k+1$ 次，则您会获得 $f(k) \times x$ 的分数，其中 $x$ 为测试点所属的子任务分值，$f(k)$ 的定义如下：

$$f(k)=\frac {1}{10}\times \begin{cases} 11-k & 4\le k\le 5 \\ 8-\left\lfloor\frac k2\right\rfloor & 6\le k\le 11\\ 1 & 12\le k\le 19\\ 0 & k\ge 20 \end{cases} $$

每个子任务取各个测试点得分的最小值。