Description

Given a sequence of length $n$, $[a_1, a_2, \ldots, a_n]$, where each number is a positive integer.

You need to find how many pairs $(i, j)$ satisfy $1 \le i \le j \le n$ and $\gcd(a_i, a_{i+1}, \ldots, a_j) \operatorname{xor} (a_i \operatorname{or} a_{i+1} \operatorname{or} \cdots \operatorname{or} a_j) = k$, where $\operatorname{xor}$ denotes bitwise XOR and $\operatorname{or}$ denotes bitwise OR.

Input Format

The first line contains two integers $n$ and $k$.

The second line contains $n$ integers $a_1, a_2, \cdots, a_n$.

Output Format

Output the number of valid pairs $(i, j)$.

5 6
2 4 3 4 2

8

Hint

• For $30\%$ of the testdata, $n \le 500$.
• For $60\%$ of the testdata, $n \le 100000$.
• For $100\%$ of the testdata, $1 \le n, a_i \le 500000$.

Translated by ChatGPT 5