Toàn mới nhận được ~k~ phiếu giảm giá cho các cửa hàng bánh kẹo. Có ~n~ loại kẹo được bày bán ở khu Toàn sống. Có ~2^n - 1~ hãng cửa hàng khác nhau được đánh số từ 1 đến ~2^n - 1~, và hãng thứ ~i~ có mở ~a_i~ cửa hàng chi nhánh. Hãng thứ ~i~ có bán loại kẹo ~j~ (~1 \le j \le n~) nếu dạng biểu diễn nhị phân của ~i~ có chứa bit thứ ~j~. Toàn muốn mua được đủ một số loại kẹo Toàn thích, và dùng hết đúng ~k~ phiếu giảm giá. Nhưng mỗi ngày, Toàn tùy hứng thay đổi sở thích ăn kẹo.

Cho ~q~ truy vấn, truy vấn thứ ~i~ là các loại kẹo mà Toàn muốn ăn vào ngày thứ ~i~, giúp Toàn đếm xem có bao nhiêu cách chọn ~k~ cửa hàng khác hãng đôi một với nhau, và có thể mua không thiếu các loại kẹo Toàn thích.

Tóm tắt: Cho các số nguyên dương ~a_1, a_2, \dots, a_{2^n-1}~ (~n \le 20~). Cho ~q~ (~q \le 10^5~) truy vấn, mỗi truy vấn gồm một số nguyên ~x~ (~0 \le x \le 2^n~), tính tổng ~a_{i_1} \times a_{i_2} \times \dots \times a_{i_k}~ của tất cả bộ số ~i_1, \dots, i_k~ (~i_1 < i_2 < \dots < i_k~) sao cho ~(i_1 \lor i_2 \lor \dots \lor i_k) \land x = x~, với ~\lor~ là phép OR và ~\land~ là phép AND.

Yêu cầu: Hãy tính tổng số kẹo của bạn cho mỗi truy vấn.

Input

• Dòng thứ nhất chứa số ~n, k~ (~k \le 3, n \le 20~).
• Dòng thứ hai chứa dãy số ~a_1, a_2, \dots, a_{2^n-1}~ (~0 \le a_i \le 10^9~).
• Dòng thứ ba chứa ~q~ (~q \le 10^5~).
• Dòng thứ 4 đến ~q+3~: chứa một số nguyên ~x~ (~0 \le x \le 2^n~), nếu dạng biểu diễn nhị phân của ~x~ có chứa bit ~j~ thì hôm đó Toàn muốn ăn loại kẹo ~j~.

Output

• Gồm ~q~ dòng, mỗi dòng thứ ~i~ là kết quả truy vấn thứ ~i~.

Sample Input 1

2 2
1 2 3
1
1

Sample Output 1

11