Trung tâm điều khiển

Một trung tâm điều khiển đang quản lý \(n\) thiết bị, được đánh số từ \(1\) đến \(n\). Mỗi thiết bị thứ \(i\) được gán một mã đặc trưng \(a_i\), trong đó các bit \(1\) trong biểu diễn nhị phân của \(a_i\) biểu thị những tính năng mà thiết bị đó hỗ trợ.

Hai thiết bị được xem là có tính năng chung nếu mã đặc trưng của chúng có ít nhất một bit \(1\) ở cùng vị trí. Nói cách khác, thiết bị \(i\) và thiết bị \(j\) có tính năng chung khi \(a_i \& a_j \neq 0\), trong đó \(\&\) là phép toán AND trên bit.

Yêu cầu: Với mỗi thiết bị \(i\) từ \(1\) đến \(n\), hãy đếm số lượng thiết bị \(j\) thỏa mãn \(a_j \& a_i \neq 0\).

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) — số lượng thiết bị \((1 \leq n \leq 2 \times 10^5)\).

• Dòng thứ hai chứa \(n\) số nguyên không âm \(a_1, a_2, \ldots, a_n\) — mã đặc trưng của các thiết bị \((0 \leq a_i \leq 10^6)\).

Output

• In ra \(n\) dòng. Dòng thứ \(i\) chứa số lượng thiết bị \(j\) thỏa mãn \(a_j & a_i \neq 0\).

Example

 5
 3 7 2 9 2

 5
 5
 4
 3
 4

Với thiết bị \(1\), \(a_1=3\). Cả \(5\) thiết bị đều có ít nhất một tính năng chung với thiết bị này, nên đáp án là \(5\).
Với thiết bị \(2\), \(a_2=7\). Cả \(5\) thiết bị đều có ít nhất một tính năng chung với thiết bị này, nên đáp án là \(5\).
Với thiết bị \(3\), \(a_3=2\). Có \(4\) thiết bị có ít nhất một tính năng chung với thiết bị này, nên đáp án là \(4\).
Với thiết bị \(4\), \(a_4=9\). Có \(3\) thiết bị có ít nhất một tính năng chung với thiết bị này, nên đáp án là \(3\).
Với thiết bị \(5\), \(a_5=2\). Có \(4\) thiết bị có ít nhất một tính năng chung với thiết bị này, nên đáp án là \(4\).

Scoring

• Subtask 1 (50 điểm): \(1 \leq n \leq 100\).

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