Cho một dãy số gồm \(n\) phần tử, nhiệm vụ của bạn là tính toán với mỗi phần tử \(x\):

1. Số phần tử \(y\) sao cho \(x\) | \(y\) \(=\) \(x\)
2. Số phần tử \(y\) sao cho \(x\) & \(y\) \(=\) \(x\)
3. Số phần tử \(y\) sao cho \(x\) & \(y\) \(\neq\) \(0\)

Input

• Dòng đầu tiên gồm số nguyên \(n\): kích thước của dãy số
• Dòng tiếp theo gồm \(n\) số nguyên \(x_1, x_2,...,x_n\): các phần tử của dãy số

Constraints

• \(1 \leq n \leq 2\cdot 10^5\)
• \(1 \leq x_i \leq 10^6\)

Output

• In ra \(n\) dòng, mỗi dòng là đáp án của các thao tác với phần tử đang xét

Example

5
3 7 2 9 2

3 2 5
4 1 5
2 4 4
1 1 3
2 4 4