"Reng reng reng..." – tiếng chuông kết thúc môn thi cuối cùng của kỳ thi đại học vang lên, ba năm thanh xuân như ngưng đọng trong khoảnh khắc này. Niềm vui tốt nghiệp xen lẫn nỗi buồn chia tay. Những tiếng cười và giọt nước mắt của hơn một ngàn ngày đêm giờ đây dồn lại trong buổi liên hoan chia tay – một khoảnh khắc không thể nào quên!

Mô tả đề bài

Thầy giáo không hài lòng với buổi diễn tập đầu tiên. Thay vì chọn ngẫu nhiên theo số thứ tự học sinh để lấy ước chung lớn nhất (GCD), thầy đã đánh giá năng lực cho từng học sinh.

Bây giờ thầy muốn chọn $k$ học sinh từ $n$ bạn sao cho độ ăn ý của họ là lớn nhất. Ở đây, độ ăn ý được định nghĩa là ước chung lớn nhất của năng lực các bạn được chọn.

Thầy không biết chính xác sẽ chọn bao nhiêu bạn, vì mỗi tiết mục cần số người khác nhau. Nên bạn cần giúp thầy tính giá trị GCD lớn nhất có thể đạt được cho mỗi $k=1\dots n$.

Định dạng vào

• Dòng 1: số nguyên $n$
• Dòng 2: $n$ số nguyên – năng lực của từng học sinh

Định dạng ra

• In $n$ dòng: dòng thứ $i$ là độ ăn ý lớn nhất có thể có nếu chọn đúng $i$ học sinh

Input

4
1 2 3 4

Output

4
2
1
1

Giải thích

• Chọn 1 học sinh: chọn bạn có năng lực 4 → GCD = 4
• Chọn 2 học sinh: chọn bạn 2 và 4 → GCD = 2
• Chọn 3 hoặc 4 học sinh: GCD không thể lớn hơn 1

Ràng buộc

• $n\le {10}^4$
• Mỗi năng lực $a_i\le {10}^6$