how to count numbers of pairs in array of size n whose xor is equal than x for each value of 0<=x<=k ?

1<=n<=100000

1<=a[i]<=100000000

1<=k<=100000

If it is a question on any site , can you post the link of the question

This is question from Zs contest for placement.

Give some example

I have found a link for you

https://codeforces.com/blog/entry/59579

But I am thinking on an easier solution as well

Are you sure about the value of a[i] ??

Input

3 2

1 2 3

Output

0 1 1

Explanation

N=3 k=2

1^2=3

2^3=1

1^3=2

0 comes 0 times

1 comes 1 times

2 comes 1 times

Yes

Well you can do it like:

- Split the number into groups based on its largest 13 bits, cause they have to be exactly the same.
- Now in each group the numbers are limited at 2 ^ 17. If the group have less than 1000 elements, brute force it. Else, use Walsh Hamadard.

Complexity for Walsh is 2 ^ 17 * 17, and there are at most 100 groups containing more than 1000. The brute force sums up to at most 1000 * 1000 * 100 = 1e8 too.