Đã đến tuần thi cuối kỳ năm cuối của Busy Beaver, và cậu ấy vừa nhớ ra danh sách các hoạt động phải hoàn thành trước khi tốt nghiệp mà cậu đã nhận được trong buổi định hướng sinh viên năm nhất.

Bạn được cho một mảng gồm $N$ số $a_1, \ldots, a_N$, trong đó $a_i$ đại diện cho niềm vui khi hoàn thành hoạt động thứ $i$.

Do thời gian hạn hẹp tại MIT, cậu ấy quyết định chỉ hoàn thành một đoạn con liên tiếp các hoạt động này. Ngoài ra, để tận dụng tối đa, đoạn con đó phải chứa ít nhất hai hoạt động.

Trong lúc trì hoãn việc ôn thi cuối kỳ, cậu ấy đã nghĩ ra một cách tính điểm tinh vi cho một đoạn con. Điểm của đoạn con từ chỉ số $l$ đến $r$ là giá trị XOR nhỏ nhất của hai hoạt động phân biệt. Một cách hình thức, đoạn con từ chỉ số $l$ đến $r$ có điểm số là $\min\limits_{l \leq i < j \leq r} a_i \oplus a_j$.

Số yêu thích của Busy Beaver là $K$, vì vậy cậu ấy muốn tính số lượng các đoạn con có điểm số bằng $K$. Bạn có thể giúp cậu ấy không?

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $N, K$ ($2 \le N \le 10^5$, $0 \le K < 2^{30}$).

Dòng thứ hai chứa $N$ số nguyên cách nhau bởi dấu cách $a_1, \dots, a_N$ ($1 \le a_i < 2^{30}$).

Dữ liệu ra

In ra một số nguyên duy nhất: số lượng các đoạn con liên tiếp có độ dài ít nhất hai với điểm số bằng $K$.

Nhiệm vụ con

• ($15$ điểm) $N \leq 5000$.
• ($10$ điểm) $K = 0$.
• ($25$ điểm) Mảng $a$ được sắp xếp theo thứ tự không giảm ($a_{1} \leq \ldots \leq a_{N}$).
• ($50$ điểm) Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

5 2
1 3 1 4 5

Ví dụ 1

3

Ghi chú

Có ba đoạn con cần được đếm:

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