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 1: Hai số nguyên \(N\) và K (\(1 \le N \le 10^5, 1 \le K \le 20\)).
• Dòng 2: \(N\) số nguyên \(a_1, a_2, \dots, a_N\) (\(0 \le a_i < 2^K\)).

Định dạng đầu ra

• In ra số lượng cặp \((i, j)\) (\(1 \le i < j \le N\)) có \(a_i \text{ OR } a_j = 2^K - 1\).

Ví dụ

Input:

4 3
1 2 4 7

Output:

3

Giải thích: Các cặp có OR bằng 7 (\(111_2\)) là \((1, 7)\), \((2, 7)\), \((4, 7)\).

Ràng buộc & Subtasks