♪ Jeremiah 是一只牛蛙
他是我的好朋友 ♪

在一条直线上有 $n$ 朵睡莲，从 $1$ 到 $n$ 编号。第 $i$ 朵睡莲上有一个正整数 $x_i$，且序列 $(x_i)_{1 \le i \le n}$ 是严格单调递增的。

现在有三只青蛙。

每一对睡莲 $(a, b)$（其中 $a < b$）必须分配给青蛙 1、青蛙 2 或青蛙 3 中的某一只。

如果睡莲对 $(i, j)$ 属于某只青蛙，且 $x_i$ 整除 $x_j$，那么这只青蛙就可以从睡莲 $i$ 跳到睡莲 $j$（$j > i$）。

请将所有的睡莲对分配给这三只青蛙，使得没有任何一只青蛙能够进行超过 3 次连续的跳跃。

输入格式

第一行包含一个正整数 $n$ ($1 \le n \le 1000$)，表示睡莲的数量。

第二行包含 $n$ 个正整数 $x_i$ ($1 \le x_i \le 10^{18}$)，表示每朵睡莲上的数字。

输出格式

输出 $n - 1$ 行。在第 $i$ 行中，输出 $i$ 个数，其中第 $j$ 个数表示睡莲对 $(j, i + 1)$ 所分配给的青蛙编号（1、2 或 3）。

子任务

如果在你的方案中，某只青蛙可以进行 $k$ 次连续跳跃（其中 $k > 3$），但没有任何一只青蛙可以进行 $k + 1$ 次连续跳跃，那么你该测试点的得分将为 $f(k) \cdot x$ 分，其中：

$$f(k) = \frac{1}{10} \cdot \begin{cases} 11 - k & \text{if } 4 \le k \le 5, \\ 8 - \lfloor k/2 \rfloor & \text{if } 6 \le k \le 11, \\ 1 & \text{if } 12 \le k \le 19, \\ 0 & \text{if } k \ge 20, \end{cases}$$

且 $x$ 是该子任务的总分。

一个子任务的得分等于你的方案在所有该子任务测试点中获得的最低分。

样例

输入样例 1

8
3 4 6 9 12 18 36 72

输出样例 1

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

输入样例 2

2
10 101

输出样例 2

1

说明

样例 1 说明：

青蛙分别用蓝色 (1)、绿色 (2) 和红色 (3) 标记。

蓝色青蛙可以从睡莲 $x_1 = 3$ 跳到睡莲 $x_4 = 9$，然后跳到睡莲 $x_7 = 36$，再跳到 $x_8 = 72$。这是所有青蛙中唯一能进行的 3 次连续跳跃。

绿色青蛙可以从睡莲 $x_2 = 4$ 跳到睡莲 $x_5 = 12$，再跳到 $x_7 = 36$，因为 4 整除 12 且 12 整除 36。这是 2 次连续跳跃。

红色青蛙不能从睡莲 $x_2 = 4$ 跳到睡莲 $x_3 = 6$，因为 6 不能被 4 整除。

没有青蛙可以进行超过 3 次连续跳跃。