Một dãy số nguyên dương \((x_1,\ldots,x_m)\) được gọi là tốt nếu \(x_1=1\) và với mỗi \(1<j\le m\), ta có \(x_j=x_{j-1}+1\) hoặc \(x_j=x_k\cdot x_l\) với một cặp chỉ số \(k,l\) nào đó thỏa mãn \(0<k\le l<j\).

Chẳng hạn, cả hai dãy \((1,1)\) và \((1,2)\) đều tốt, nhưng dãy \((1,3)\) không tốt.

Cho \(n\) số nguyên \(w_1,\ldots,w_n\). Trọng số của một dãy số nguyên \((x_1,\ldots,x_m)\) thỏa mãn \(1\le x_j\le n\) với mọi \(1\le j\le m\) được định nghĩa là

Chẳng hạn, với các trọng số \(w_1=10\), \(w_2=42\), \(w_3=1\), trọng số của dãy \((1,1)\) là \(20\) và trọng số của dãy \((1,3)\) là \(11\).

Với \(1\le v\le n\), gọi \(s_v\) là trọng số nhỏ nhất có thể của một dãy tốt chứa giá trị \(v\).

Nhiệm vụ của bạn là xác định các giá trị \(s_1,\ldots,s_n\).

Dữ liệu vào

Dòng đầu tiên chứa số nguyên \(n\), là số lượng trọng số.

\(n\) dòng tiếp theo lần lượt chứa các trọng số nguyên \(w_1,\ldots,w_n\), mỗi dòng một số.

Dữ liệu ra

In \(n\) dòng lần lượt chứa \(s_1,\ldots,s_n\).

Ràng buộc

• \(1\le n\le 30\,000\).
• \(1\le w_i\le 10^6\) với mọi \(1\le i\le n\).

Phân nhóm

Các bộ kiểm thử được chia thành các nhóm, mỗi nhóm có một số điểm. Để nhận được điểm của một nhóm, chương trình phải giải đúng tất cả các bộ kiểm thử trong nhóm đó. Điểm cuối cùng là điểm cao nhất của một lần nộp bài.

1. \(11\) điểm: \(n\le 10\).
2. \(10\) điểm: \(n\le 300\) và \(w_1=\cdots=w_n=1\).
3. \(10\) điểm: \(n\le 300\) và \(w_1=\cdots=w_n\).
4. \(9\) điểm: \(n\le 1400\) và \(w_1=\cdots=w_n=1\).
5. \(45\) điểm: \(n\le 5000\).
6. \(15\) điểm: không có ràng buộc bổ sung.

Ví dụ

3
10
42
1

10
52
53