Toàn mới nhận được $𝑘$ phiếu giảm giá cho các cửa hàng bánh kẹo. Có $𝑛$ loại kẹo được bày bán ở khu Toàn sống. Có $2n-1$ hãng cửa hàng khác nhau được đánh số từ 1 đến $2n-1$, và hãng thứ $i$ có mở ${𝑎}_i$ cửa hàng chi nhánh. Hãng thứ $𝑖$ có bán loại kẹo $𝑗(1\le 𝑗\le 𝑛)$ nếu dạng biểu diễn nhị phân của $𝑖$ có chứa bit thứ $𝑗$. Toàn muốn mua được đủ một số loại kẹo Toàn thích, và dùng hết đúng $𝑘$ 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 $𝑞$ truy vấn, truy vấn thứ $𝑖$ là các loại kẹo mà Toàn muốn ăn vào ngày thứ $𝑖$, giúp Toàn đếm xem có bao nhiêu cách chọn $𝑘$ 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 ${𝑎}_1,{𝑎}_2,...,{𝑎}_{2n-1}(𝑛\le 20)$. Cho $𝑞(𝑞\le {10}^5)$ truy vấn, mỗi truy vấn gồm một số nguyên $𝑥(0\le 𝑥\le 2n)$, tính tổng ${𝑎}_{i1}\times {𝑎}_{i2}\times ...\times {𝑎}_{ik}$ của tất cả bộ số ${𝑖}_1,...,{𝑖}_k({𝑖}_1<{𝑖}_2<...<{𝑖}_k)$ sao cho $({𝑖}_1\vee {𝑖}_2\vee ...\vee {𝑖}_k)\wedge 𝑥=𝑥$, với ∨ là phép OR và ∧ là phép AND.

Yêu cầu: Hãy tính tổng số kẹo của bạn từ vị trí $l$ đến vị trí $r$.

Dữ liệu:

• Dòng thứ nhất chứa số $𝑛,𝑘(𝑘\le 3,𝑛\le 20)$
• Dòng thứ hai chứa dãy số ${𝑎}_1,{𝑎}_2,...,{𝑎}_{2n-1}(0\le {𝑎}_i\le {10}^9)$;
• Dòng thứ ba chứa $𝑞(𝑞\le {10}^5)$;
• Dòng thứ 4...𝑞+3: chứa một số nguyên $𝑥(0\le 𝑥\le 2n)$, nếu dạng biểu diễn nhị phân của $𝑥$ có chứa bit 𝑖 thì hôm đó Toàn muốn ăn loại kẹo $𝑖$.

Kết quả: Gồm $𝑞$ dòng, mỗi dòng thứ $𝑖$ là kết quả truy vấn thứ ~𝑖`.

Ví dụ:

input

2 2
1 2 3
1
1

output

11

Ràng buộc:

• Subtask 1: $𝑘=1,𝑛\le 10$ (5%)
• Subtask 2: $𝑘=1,𝑛\le 17$ (10%)
• Subtask 3: $𝑘=1,𝑛\le 20$ (25%)
• Subtask 4: $𝑘=2,𝑛\le 20$ (35%)
• Subtask 5: $𝑘=3,𝑛\le 20$ (25%)