Nhận thấy sắp tới ngày quốc tế thiếu nhi (International Children's Day), trường tiểu học Bedao tổ chức một số hoạt động chào mừng, trường sẽ tổ chức một buổi phát kẹo. Trường dự định phát kẹo cho ~N~ em học sinh nhưng với bản tính tương thân tương ái "có bao nhiêu chia bấy nhiêu" các em thường sẽ lấy số kẹo của mình chia đều cho các em có số thứ tự lớn hơn mình, sau cùng sẽ giữ lại phần không thể chia. Hay với em học sinh có số thứ tự ~i~ thì em sẽ chia kẹo mình cho em học sinh số thứ tự ~j~ sao cho ~(i < j)~ và số kẹo học sinh ~i~ chia cho từng em học sinh ~j~ sẽ như nhau. Hỏi sau khi phát kẹo và các em học sinh chia kẹo cho nhau xong thì số kẹo của từng em học sinh sẽ là bao nhiêu ?

Input

• Dòng thứ nhất chứa ~1~ số nguyên ~N~ ~(1 \le N \le 10^6)~.
• Dòng thứ hai chứa ~N~ số nguyên dương ~A_1, A_2 , \dots , A_N~ ~(1 \le A_i \le 10^9)~, mỗi số được cách nhau bởi ~1~ dấu cách.

Output

• Ghi ra ~N~ số nguyên dương là số kẹo sau cùng của ~N~ học sinh.

Sample Input

3 
3 2 1

Sample Output

1 0 5

Subtask

• ~50\%~ số test có ~N \le 3000~
• ~50\%~ số test tiếp theo có ~N \le 10^6~

Note

• Em học sinh ~1~ chia cho em học sinh ~2~ và ~3~ mỗi em ~1~ cái kẹo. Số kẹo giờ còn là ~[1 , 3 , 2]~.
• Em học sinh ~2~ chia cho em học sinh ~3~ ~3~ cái kẹo . Số kẹo giờ còn là ~[1 , 0 , 5]~.