Tý cần giải bài toán sau:

Trong một giải đấu game, mỗi người chơi có mã năng lực \(A[i]\) (\(0 \le A[i] < 2^K\)). Người ta muốn tìm những cặp game thủ có XOR mã năng lực đúng bằng một giá trị \(X\) cho trước, vì những cặp này sẽ tạo ra trận đấu cân bằng nhất.

Hãy đếm số cặp \((i < j)\) thỏa mãn \(A[i] \oplus A[j] = X\).

Đầu vào:

• Dòng 1: \(N, K\) (\(N \le 10^5\), \(K \le 20\))
• Dòng 2: \(N\) số nguyên \(A[1..N]\)
• Dòng 3: số \(X\) (\(0 \le X < 2^K\))

Đầu ra:

• Số cặp thỏa mãn XOR bằng \(X\).

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

• Dòng đầu chứa số nguyên \(N\) và \(Q\) (\(N, Q \le 10^5\)).
• \(N-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) mô tả một cạnh.

Định dạng đầu ra

• In ra kết quả của từng truy vấn trên một dòng.

Ví dụ

Input:

5 3
1 2
1 3
2 4
2 5
2 3

Output:

3

Ràng buộc