Cho mảng \(A\) gồm N số nguyên không âm và một số nguyên K. Bạn cần đếm xem có bao nhiêu cặp chỉ số \((i, j)\) thỏa mãn \(1 \le i < j \le N\) sao cho giá trị Bitwise XOR của chúng nhỏ hơn K (\(A[i] \oplus A[j] < K\)).

Hãy phát triển giải thuật trên Bitwise Trie để xử lý bài toán hiệu quả.

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên dương \(N\) và K (\(2 \le N \le 10^5, 0 \le K \le 10^9\)).
• Dòng hai chứa \(N\) số nguyên không âm \(a_1, a_2, \dots, a_N\) cách nhau bởi dấu cách (\(0 \le a_i \le 10^9\)).

Định dạng đầu ra

• Một số nguyên duy nhất là số lượng cặp chỉ số thỏa mãn yêu cầu.

Ví dụ

Input:

4 6
3 10 5 25

Output:

1

Giải thích

Chỉ có cặp \((3, 10)\)? Không, \(3 \oplus 5 = 6 \not < 6\). Có cặp nào: \(3 \oplus 10 = 9\), \(3 \oplus 25 = 26\), \(10 \oplus 5 = 15\), \(10 \oplus 25 = 19\), \(5 \oplus 25 = 28\). Chờ, ví dụ trên có cặp nào nhỏ hơn 6? Không có cặp nào! Hãy dùng ví dụ chuẩn xác: Mảng: 3 10 5 2 và \(K = 6\). Cặp:

• \(3 \oplus 5 = 6 \not < 6\)
• \(3 \oplus 2 = 1 < 6\) (thỏa mãn) - \(10 \oplus 5 = 15 \ge 6\)
• \(10 \oplus 2 = 8 \ge 6\)
• \(5 \oplus 2 = 7 \ge 6\) Tổng cộng: 1 cặp.

Input chuẩn:

4 6
3 10 5 2

Output chuẩn:

1

Ràng buộc

• 30% số điểm ứng với \(N \le 1000\)
• 70% số điểm còn lại không có ràng buộc gì thêm.
• Kết quả có thể vượt quá giới hạn số nguyên 32-bit.