101 Things To Do Before You Graduate

Busy Beaver の大学最終学年の期末試験週間が始まりました。彼は、1年生のオリエンテーションで受け取った、卒業までに完了すべき活動リストのことを思い出しました。

$N$ 個の数値からなる配列 $a_1, \ldots, a_N$ が与えられます。ここで $a_i$ は $i$ 番目の活動を完了したときの喜びを表します。

MIT での限られた時間のため、彼はこれらの活動のうち連続する部分列のみを完了することに決めました。さらに、最大限に楽しむために、その部分列には少なくとも 2 つの活動が含まれていなければなりません。

期末試験の準備を先延ばしにしている間、彼は部分列を評価する洗練された方法を思いつきました。インデックス $l$ から $r$ までの部分列のスコアは、その中の異なる 2 つの活動の XOR の最小値です。形式的には、インデックス $l$ から $r$ までの部分列のスコアは $\min\limits_{l \leq i < j \leq r} a_i \oplus a_j$ となります。

Busy Beaver のお気に入りの数は $K$ です。スコアが $K$ となる部分列の数を計算するのを手伝ってください。

入力

1 行目に 2 つの整数 $N$ と $K$ が与えられます ($2 \le N \le 10^5$, $0 \le K < 2^{30}$)。

2 行目に $N$ 個の空白区切りの整数 $a_1, \dots, a_N$ が与えられます ($1 \le a_i < 2^{30}$)。

出力

スコアが $K$ となる、サイズが少なくとも 2 である連続する部分列の数を 1 つの整数で出力してください。

小課題

• ($15$ 点) $N \leq 5000$。
• ($10$ 点) $K = 0$。
• ($25$ 点) 配列 $a$ は昇順にソートされている ($a_{1} \leq \ldots \leq a_{N}$)。
• ($50$ 点) 追加の制約なし。

入出力例

入力 1

5 2
1 3 1 4 5

出力 1

3

注記

カウントされるべき部分列は以下の 3 つです。

• $l = 1, r = 2$
• $l = 2, r = 3$
• $l = 2, r = 4$