Trọng số tín hiệu 2

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\).

Mỗi mã truy vấn \(x\) biểu diễn một tập các đặc tính tín hiệu cần thiết dưới dạng nhị phân. Một bộ phát thứ \(i\) được xem là tương thích với mã \(x\) nếu nó chứa đầy đủ tất cả các bit \(1\) 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\) tương thích với \(x\) khi \(x & i = x\), 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 = x\).

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

4 3 1 

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.