Trọng số tín hiệu

Trong một hệ thống xử lý tín hiệu số, có \(n\) bộ phát được đánh số từ \(1\) đến \(n\). Bộ phát thứ \(i\) có cường độ tín hiệu là \(a_i\).

Hệ thống sử dụng biểu diễn nhị phân của chỉ số các bộ phát để xác định những tín hiệu có liên quan đến một mã truy vấn \(x\). Một bộ phát thứ \(i\) được xem là phù hợp với mã \(x\) nếu tất cả các bit \(1\) trong biểu diễn nhị phân của \(i\) cũng xuất hiện trong biểu diễn nhị phân của \(x\).

Nói cách khác, bộ phát thứ \(i\) phù hợp với \(x\) khi \(x & i = i\), trong đó \(&\) là phép toán AND trên bit.

Với mỗi số nguyên dương \(x\), ta định nghĩa trọng số của \(x\) là:

tức là tổng cường độ của tất cả các bộ phát thứ \(i\) thỏa mãn \(x & i = i\).

Yêu cầu: Hãy tính lần lượt các giá trị \(f(1), f(2), \ldots, f(2^{\lfloor \log_2 n \rfloor + 1} - 1)\).

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) — số lượng bộ phát \((1 \leq n \leq 10^6)\).

• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) — cường độ tín hiệu của các bộ phát \((|a_i| \leq 10^9)\).

Output

• In ra lần lượt các giá trị \(f(1), f(2), \ldots, f(2^{\lfloor \log_2 n \rfloor + 1} - 1)\) trên một dòng, các giá trị cách nhau bởi một dấu cách.

Example

3
3 2 1

3 2 6

Scoring

• Subtask 1 (30 điểm): \(1 \leq n \leq 1000\).

• Subtask 2 (30 điểm): \(1 \leq n \leq 100000\).

• Subtask 3 (40 điểm): Không có ràng buộc gì thêm.