Một dãy ước lồng nhau độ dài \(n\) gồm \(n\) số nguyên \(a_1, a_2, ..., a_n\) sao cho \(0 < a_1 < ... < a_n\) và \(a_1 | a_2 | ... | a_n\) với \(a | b\) kí hiệu số nguyên \(a\) là ước của số nguyên \(b\).

Cho số nguyên \(k\), tìm dãy ước lồng nhau dài nhất và có tổng các số trong dãy lớn nhất mà kết thúc tại \(k\).

Đầu vào

Một số nguyên \(k\) \((1 \le k \le 10^{12})\) duy nhất.

Đầu ra

Một dòng duy nhất là các phần tử của dãy tìm được, sắp xếp theo thứ tự tăng dần.

Ví dụ

Đầu vào 1:

10

Đầu ra 1:

1 5 10

Giải thích: dãy ước lồng nhau dài nhất kết thúc tại \(10\) là \(1, 2, 10\) hoặc \(1, 5, 10\), do \(1 + 5 + 10 > 1 + 2 + 10\) nên xuất ra dãy \(1, 5, 10\).

Đầu vào 2:

97

Đầu ra 2:

1 97