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

Trong một cuộc thi thể thao, mỗi vận động viên có mã số kỹ năng \(A[i]\) (\(0 \le A[i] < 2^K\)). Sức mạnh kết hợp của hai vận động viên là \(A[i] \mid A[j]\) (OR của hai mã số). Ban tổ chức muốn biết: với ngưỡng \(X\) cho trước, có bao nhiêu cặp vận động viên có sức mạnh kết hợp không vượt quá \(X\)?

Đầu vào:

• Dòng 1: \(N, K, Q\) (\(N \le 10^5\), \(K \le 20\), \(Q \le 10^5\))
• Dòng 2: \(N\) số nguyên \(A[1..N]\)
• \(Q\) dòng tiếp theo, mỗi dòng là một số \(X\) (\(0 \le X < 2^K\))

Đầu ra:

• Với mỗi truy vấn \(X\), in ra số cặp \((i < j)\) mà \(A[i] \mid A[j] \le 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