题目描述

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

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

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

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

一只青蛙可以从荷叶 $i$ 跳到荷叶 $j(j>i)$ 当且仅当 $(i,j)$ 被标记成这只青蛙且 $x_i|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

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

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

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

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

2
10 101

1

数据范围与提示

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

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

$$\begin{equation} f(x)=\frac {1}{10}\times \left\{ \begin{aligned}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{aligned} \right. \end{equation}$$

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