Ba Góc Nhìn Của Mặt Nạ · canuc80k4600

Cho một dãy số nguyên dương. Với từng giá trị đang xét, cần đếm số phần tử của chính dãy thỏa ba quan hệ bit khác nhau. Mỗi vị trí được tính riêng, kể cả khi nhiều vị trí mang cùng giá trị.

Input

Dòng đầu chứa số nguyên $n$ . Dòng thứ hai chứa $n$ số nguyên $a_{1}, a_{2}, \dots, a_{n}$ .

Output

Với mỗi $a_{i}$ , in trên một dòng ba số theo thứ tự: số vị trí $j$ có $a_{i} ∣ a_{j} = a_{i}$ ; số vị trí $j$ có $a_{i} AND a_{j} = a_{i}$ ; số vị trí $j$ có $a_{i} AND a_{j} \neq = 0$ .

Constraints

$1 \leq n \leq 2 \cdot 1 0^{5}$ .
$1 \leq a_{i} \leq 1 0^{6}$ .
Các phép | và & lần lượt là OR bit và AND bit.

Scoring

Subtask $1$ ( $50%$ số điểm): $n \leq 2000$ và $a_{i} < 2^{12}$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

4
1 2 3 4

Output

Giải thích: Với giá trị $1$ , các số là submask của $1$ chỉ có $1$ ; các số chứa bit của $1$ là $1, 3$ ; và hai số có giao bit khác rỗng với $1$ cũng là $1, 3$ . Các dòng còn lại được tính tương tự.

Phân tích: Với một mask x, điều kiện x | y = x tương đương y là submask của x; điều kiện x & y = x tương đương y là supermask của x. Quan hệ thứ ba được tính qua phần bù: x & y = 0 khi và chỉ khi y là submask của ALL xor x. Vì nhiều vị trí có thể mang cùng giá trị, ta bắt đầu bằng bảng tần suất.
Thuật toán: Gọi B là số bit đủ chứa mọi giá trị và S=2^B.
Thuật toán: 1. Đặt sub[m]=sup[m]= số lần mask m xuất hiện. 2. Chạy subset zeta trên sub, để sub[m] trở thành số phần tử là submask của m. 3. Chạy superset zeta trên sup, để sup[m] trở thành số phần tử là supermask của m. 4. Với mỗi x, in sub[x], sup[x], và n-sub[ALL xor x].
Chứng minh đúng đắn: Sau subset zeta, mỗi tần suất ban đầu tại y được cộng vào đúng các mask m chứa y, nên sub[m] đếm chính xác các y thỏa y | m = m. Tương tự, superset zeta cộng y vào đúng các m là submask của y, nên sup[m] đếm chính xác các y thỏa m & y = m.
Chứng minh đúng đắn: Cuối cùng, các giá trị không giao bit với x chính là các submask của ALL xor x; có sub[ALL xor x] vị trí như vậy. Lấy phần bù trong n cho đúng số vị trí có AND khác 0. Ba đại lượng in ra vì thế đúng theo đề.
Độ phức tạp: O(n + B·2^B) thời gian và O(2^B) bộ nhớ.