Mirko là người thích tiệc tùng nên anh đã quyết định tổ chức vô số bữa tiệc cho bạn bè của mình. Để đáp ứng nhu cầu của cả nhóm, anh ấy đã quyết định bày ~N~ bàn có kẹo trên đó. Chúng ta biết số kẹo bi trên mỗi bàn. Vào ngày đầu tiên của cõi vĩnh hằng, Mirko sẽ mời một người bạn mỗi bàn, ngày thứ hai anh ấy sẽ mời hai người bạn mỗi bàn, vào ngày thứ ba ba người bạn... Nói chung, rõ ràng là vào ngày thứ ~k~ anh ấy sẽ mời ~k~ người bạn vào mỗi bàn.

Khi bạn của anh ấy vào phòng, ~k~ người sẽ ngồi xuống mỗi bàn và họ sẽ chia số kẹo trên bàn của mình thành ~k~ phần bằng nhau càng lớn càng tốt và loại bỏ những phần còn lại có thể. Sau khi chia kẹo, vì ghen tị và nhiều lý do khác, chỉ những bàn có số lượng kẹo bình quân đầu người bằng nhau mới giao lưu với nhau. Mirko có toàn bộ thời gian để nghiên cứu động lực xã hội của các đảng phái của mình. Đầu tiên, anh ta muốn biết câu trả lời cho câu hỏi sau: Cho điểm ~s~ từ ~1~ đến ~N~, ngày sớm nhất mà một nhóm gồm chính xác ~s~ bàn giao tiếp với nhau là ngày nào?

Như thường lệ, Mirko không có khả năng tự giải quyết vấn đề của mình nên cứ vài ngày anh ấy lại đến gặp bạn và hỏi bạn số cần tìm là bao nhiêu, cho trước một chữ ~s~. Than ôi, anh ấy có cả thời gian để đặt câu hỏi, còn bạn thì không. Vì vậy, bạn sẽ viết một chương trình đưa ra các câu trả lời cần thiết của Mirko cho mỗi giây từ ~1~ đến ~N~.

Xin lưu ý: Trước mỗi bữa tiệc, Mirko gia hạn nguồn cung cấp kẹo trên mỗi bàn, nghĩa là nguồn cung cấp bằng với nguồn cung cấp trước bữa tiệc đầu tiên. Ngoài ra, tất cả mọi người sẽ rời khỏi nhóm hiện tại trước khi nhóm tiếp theo bắt đầu.

Input

• Dòng đầu tiên chứa số nguyên ~N~ ~(1 \le N \le 100)~.
• Dòng thứ hai chứa ~N~ số nguyên, số thứ ~i~ đánh dấu số kẹo trên bảng thứ ~i~.
• Các số nằm trong khoảng ~[1, 10^8]~.

Output

• In ra ~N~ dòng, mỗi dòng ghi một số nguyên.
• Dòng thứ ~s~ phải chứa số cần thiết cho một nhóm có kích thước ~s~ hoặc ~-1~ nếu sẽ không bao giờ có một nhóm có kích thước đó.

Scoring

• Trong các trường hợp thử nghiệm trị giá 30% tổng số điểm, số kẹo trên tất cả các bàn sẽ không vượt quá ~10^3~.
• Trong các trường hợp thử nghiệm có giá trị cộng thêm 30% tổng điểm, số kẹo trên tất cả các bàn sẽ không vượt quá ~10^6~.

Sample Input 1

5 
11 10 9 6 4

Sample Output 1

1
2
3
6
12

Sample Input 2

3
5 5 5

Sample Ouput 2

-1
-1
1

Sample Input 3

8
12 16 95 96 138 56 205 84

Sample Output 3

1
5
14
49
96
97
139
206

Làm rõ ví dụ đầu tiên: Vào ngày đầu tiên, mỗi bàn sẽ chỉ giao tiếp với chính mình nên câu trả lời cho các nhóm cỡ 1 là 1. Sang ngày thứ hai, những người ngồi ở bàn 1 và 2 là. sẽ nhận được 5 chiếc kẹo cho mỗi người và giao lưu cùng nhau, vì vậy câu trả lời cho nhóm cỡ 2 là 2. Vào ngày thứ ba, các bàn 1, 2 và 3 sẽ giao lưu (vì mỗi người đều có 3 chiếc kẹo). Vào ngày thứ sáu, các bàn 1, 2, 3 và 4 sẽ giao lưu với nhau (vì hiện tại mỗi người mỗi người có 1 chiếc kẹo). Cuối cùng, vào ngày thứ mười hai, tất cả các bàn sẽ giao lưu với nhau vì tất cả họ sẽ không nhận được kẹo nào trên đầu người.

Làm rõ ví dụ thứ hai: Tất cả các bàn đều có lượng kẹo bình quân đầu người như nhau, vì vậy một nhóm có quy mô nhỏ hơn 3 sẽ không bao giờ tồn tại.