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 ≤ 𝑗 ≤ 𝑛)~ 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} (𝑛 ≤ 20)~. Cho ~𝑞 (𝑞 ≤ 10^5)~ truy vấn, mỗi truy vấn gồm một số nguyên ~𝑥 (0 ≤ 𝑥 ≤ 2n)~, tính tổng ~𝑎_{i1}×𝑎_{i2}×...×𝑎_{ik}~ của tất cả bộ số ~𝑖_1,..., 𝑖_k (𝑖_1 < 𝑖_2 < ...< 𝑖_k)~ sao cho ~(𝑖_1∨𝑖_2∨...∨𝑖_k)∧𝑥 = 𝑥~, 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ố ~𝑛, 𝑘 (𝑘 ≤ 3, 𝑛 ≤ 20)~
• Dòng thứ hai chứa dãy số ~𝑎_1, 𝑎_2,..., 𝑎_{2n-1} (0 ≤ 𝑎_i ≤ 10^9)~;
• Dòng thứ ba chứa ~𝑞 (𝑞 ≤ 10^5)~;
• Dòng thứ 4...𝑞+3: chứa một số nguyên ~𝑥 (0 ≤ 𝑥 ≤ 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,𝑛 ≤ 10~ (5%)
• Subtask 2: ~𝑘 = 1,𝑛 ≤ 17~ (10%)
• Subtask 3: ~𝑘 = 1,𝑛 ≤ 20~ (25%)
• Subtask 4: ~𝑘 = 2,𝑛 ≤ 20~ (35%)
• Subtask 5: ~𝑘 = 3,𝑛 ≤ 20~ (25%)