Có ~n~ lá sen được đánh số từ ~1~ đến ~n~ xếp thành 1 hàng ngang. Trên lá sen thứ ~i~ có 1 số nguyên ~x_i~, và dãy ~(x_i)_{1\leq i \leq n}~ là dãy tăng ngặt.
Đặt 3 chú ếch lên những lá sen.
Mỗi cặp lá sen ~(a,b), a \leq b~, phải thuộc về 1 trong 3 chú ếch.
Chú ếch có thể nảy từ lá sen ~i~ sang lá sen ~j~, ~(i < j)~. Nếu cặp ~(i,j)~ thuộc về nó, đồng thời ~x_j~ chia hết cho ~x_i~
Hãy phân phối các cặp chỉ số cho những chú ếch sao cho không có chú ếch nào có thể nhảy từ lá sen này sang lá sen khác quá 3 lần liên tục.
Input
Dòng đầu tiên chứa ~1~ số nguyên ~n (1 \leq n \leq 1000)~ là số lá sen.
Dòng thứ 2 chứa ~n~ số nguyên dương ~x_i~ ~(1 \leq x_i \leq 10^{18})~ là các số nguyên ở trên từng lá sen.
Output
Xuất ra ~n-1~ dòng.
Ở dòng thứ ~i~ xuất ra ~i~ số, số thứ ~j~-th là chỉ số của chú ếch mà cặp lá sen ~(j,i+1)~ thuộc về nó.
Sample 1
Input
8
3 4 6 9 12 18 36 72
Output
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
Sample 2
Input
2
10 101
Output
1
Giải thích
Ở ví dụ đầu tiên:
Ta sẽ xét những chú ếch như sau: ếch số 1 màu xanh biển, ếch số 2 màu xanh lá, ếch số 3 màu đỏ.
Chú ếch xanh biển có thể nhảy từ lá sen có ~x_1 = 3~ tới lá sen ~x_4 = 9~ rồi nhảy sang lá sen ~x_7 = 36~ rồi tới lá sen ~x_8 = 72~. Đây là 3 cú nhảy liên tiếp duy nhất mà chú ếch nào cũng thực hiện được.
Chú ếch xanh lá có thể bắt đầu từ lá sen ~x_2 = 4~ tới lá sen ~x_5 = 12~ rồi tới ~x_7 = 36~ (vì 12 chia hết cho 4 và 36 chia hết cho 12).Tổng cộng có 2 lần nhảy liên tiếp.
Chú ếch đỏ không thể nhảy từ lá sen có ~x_2 = 4~ đến lá sen có ~x_3=6~ vì 6 không chia hết cho 4.
Không có chú ếch nào có thể thực hiện quá 3 lần nhảy liên tiếp.
Subtask
- ~6~ test đầu tiên có ~n \leq 30~.
- ~17~ test còn lại không ràng buộc gì thêm.
Nếu trong đáp án của bạn một vài chú ếch có thể thực hiện ~k~ cú nhảy liên tiếp,~k > 3~, nhưng không có chú ếch khác nào có thể thực hiện ~k+1~ cú nhảy liên tiếp thì số điểm bạn nhận được cho test đó là ~f(k)\times x~.
~f(k)~ được xác định bởi:
~f(k) = \frac{1}{10} \times \begin{cases} {11 - k} & {(4 \leq k \leq 5)},\\ {8 - \lfloor k/2 \rfloor }&(6 \leq k \leq 11),\\ {1}&{(12 \leq k \leq 19)},\\ {0}&{(k \geq 20)} \end{cases}~
Điểm của test là= ~f(k) \times x~. Điểm của bài là tổng điểm các test.
Bình luận