There are ~n~ water lilies, numbered ~1~ through ~n~, in a line. On the ~i^\text{th}~ lily there is a positive integer ~x_i~, and the sequence ~(x_i)_{1 \le i \le n}~ is strictly increasing.

Enter three frogs.

Every pair of water lilies ~(a, b)~, where ~a < b~, must belong to frog ~1~, frog ~2~, or frog ~3~.

A frog can hop from water lily ~i~ to water lily ~j > i~ if the pair ~(i, j)~ belongs to it, and ~x_i~ divides ~x_j~.

Distribute the pairs among the frogs such that no frog can make more than ~3~ consecutive hops.

Input Specification

The first line contains a positive integer ~n~ ~(1 \le n \le 1\,000)~, the number of water lilies.

The second line contains ~n~ positive integers ~x_i~ ~(1 \le x_i \le 10^{18})~, the numbers on the water lilies.

Output Specification

Output ~n-1~ lines. In the ~i^\text{th}~ line, output ~i~ numbers, where the ~j^\text{th}~ number is the label of the frog to which ~(j, i+1)~ belongs.

Constraints

Subtask	Points	Constraints
~1~	~10~	~n \le 30~
~2~	~100~	No additional constraints.

If in your solution some frog can make ~k~ consecutive hops, where ~k > 3~, but no frog can make ~k+1~ consecutive hops, your score for that test case is ~f(k) \cdot x~ points, where

$$\displaystyle f(x) = \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}$$

and ~x~ is the number of points for that subtask.

The score for some subtask equals the minimum score which your solution gets over all test cases in that subtask.

Sample Input 1

8
3 4 6 9 12 18 36 72

Sample Output 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

Explanation

The frogs are marked blue (~1~), green (~2~), and red (~3~).

The blue frog can hop from water lily ~x_1 = 3~ to water lily ~x_4 = 9~, then to water lily ~x_7 = 36~, and then to ~x_8 = 72~. These are the only three consecutive hops any frog can make.

The green frog can hop from water lily ~x_2 = 4~ to water lily ~x_5 = 12~, and then to ~x_7 = 36~, because ~4~ divides ~12~, and ~12~ divides ~36~. Those are two consecutive hops.

The red frog cannot hop from water lily ~x_2 = 4~ to water lily ~x_3 = 6~ because ~6~ is not divisible by ~4~.

No frog can make more than three consecutive hops.

Sample Input 2

2
10 101

Sample Output 2

1