Given an array of length N and an integer K. Find the number of pairs (i, j) such that (i != j) and (A[i] xor A[j]) = X, for each X ranging from 0 to K.

Constraints

N <= 1e5

A[i] <= 1e8

K <= 1e5

Example

Input

7

1 1 2 2 3 3 4

4

Output

3 3 3 4 0

I tried finding the editorial for the below problem, but was unable to find one which I could understand. Can someone explain the solution for it?

https://www.spoj.com/problems/CNTINDX2/

Given N intervals and Q queries of the form L and R. Find the largest sized interval completely lying inside the query range. 1 <= N, Q, L, R <= 1e6.