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ố.

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.

Constraints

• \(1 \le n \le 2 \times 10^5\)
• \(1 \le x_i \le 10^6\)

Example

Sample Input

5
3 7 2 9 2

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