Contiguous Subsequence XOR

Time limit1sMemory limit512 MB

Summary

Count contiguous subsequences of the given sequence whose bitwise XOR is less than K.

Level: Medium7 of 10
Topics: Bit manipulation, Trie, Prefix sum
Solved: No attempts yet

Problem

You are given a sequence $A_1, A_2, \dots, A_N$ of length $N$ . Count the contiguous subsequences whose XOR is less than $K$ .

A contiguous subsequence is $A_i, A_{i+1}, \dots, A_j$ for a pair of indices with $i \le j$ . Its XOR is $A_i \oplus A_{i+1} \oplus \dots \oplus A_j$ , where $\oplus$ is the bitwise exclusive or.

Two contiguous subsequences with a different start position or a different end position count separately, even when their elements have the same values.

Input

The first line contains $N$ and $K$ , separated by a space. ( $1 \le N \le 100{,}000$ , $1 \le K \le 1{,}000{,}000$ )

The second line contains $A_1, A_2, \dots, A_N$ in order, separated by spaces. ( $1 \le A_i \le 100{,}000$ )

Output

Print the number of contiguous subsequences whose XOR is less than $K$ on the first line.

Examples3

Example 1
Input
```
5 2
4 1 3 2 7
```
Expected output
```
3
```
Example 2
Input
```
1 1
1
```
Expected output
```
0
```
Example 3
Input
```
1 2
1
```
Expected output
```
1
```