Phòng thí nghiệm JOI nuôi \(2^L\) con rắn độc, đánh số từ \(0\) đến \(2^L-1\). Cơ thể mỗi con được chia thành \(L\) phần theo thứ tự từ đầu đến đuôi; mỗi phần có màu xanh dương hoặc đỏ. Với con rắn thứ \(i\), viết biểu diễn nhị phân đủ \(L\) chữ số của \(i\) dưới dạng:

• Nếu \(c_k=0\), phần thứ \(k\) tính từ đầu của con rắn \(i\) có màu xanh dương.
• Nếu \(c_k=1\), phần thứ \(k\) tính từ đầu của con rắn \(i\) có màu đỏ.

Mỗi con rắn có một độ độc, là số nguyên từ \(0\) đến \(9\). Bạn được cho xâu \(S\) có độ dài \(2^L\), chỉ gồm các chữ số từ 0 đến 9. Ký tự thứ \(i\) của \(S\) (\(1\le i\le2^L\)) cho biết độ độc của con rắn mang số \(i-1\).

Do di chuyển nhanh, các con rắn thường trốn khỏi phòng thí nghiệm. Những người dân sống gần đó nhìn thấy chúng và gửi phản ánh đến phòng thí nghiệm JOI.

Bạn được cho thông tin phản ánh trong \(Q\) ngày. Thông tin của ngày thứ \(d\) là xâu \(T_d\) có độ dài \(L\), chỉ gồm 0, 1, ?. Với mỗi vị trí \(j\) (\(1\le j\le L\)):

• Nếu ký tự thứ \(j\) của \(T_d\) là 0, phần thứ \(j\) tính từ đầu của mọi con rắn trốn ra trong ngày đó đều có màu xanh dương.
• Nếu ký tự đó là 1, phần thứ \(j\) tính từ đầu của mọi con rắn trốn ra trong ngày đó đều có màu đỏ.
• Nếu ký tự đó là ?, người dân không cung cấp thông tin về phần thứ \(j\) của các con rắn trốn ra trong ngày đó.

Tất cả thông tin phản ánh đều chính xác. Nhân viên phòng thí nghiệm bắt lại toàn bộ các con rắn trốn ra ngay trong ngày. Một con rắn có thể lại trốn ra vào một ngày khác.

Để đánh giá mức độ nguy hiểm, giáo sư K, giám đốc phòng thí nghiệm JOI, muốn biết tổng độ độc của tất cả các con rắn có thể đã trốn ra, tức là có màu sắc phù hợp với thông tin phản ánh. Cho xâu \(S\) và thông tin của \(Q\) ngày, hãy tính tổng này cho từng ngày.

Lưu ý: giới hạn bộ nhớ của bài này nhỏ, chỉ \(64\) MB.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu chứa hai số nguyên \(L,Q\), cách nhau bởi dấu cách, lần lượt là số phần trên cơ thể mỗi con rắn và số ngày có thông tin phản ánh.
• Dòng thứ hai chứa xâu \(S\) độ dài \(2^L\), mô tả độ độc của các con rắn.
• Dòng thứ \(d\) trong \(Q\) dòng tiếp theo chứa xâu \(T_d\) độ dài \(L\), là thông tin phản ánh của ngày thứ \(d\).

Dữ liệu ra

Ghi \(Q\) dòng. Dòng thứ \(d\) chứa một số nguyên là tổng độ độc của các con rắn có thể đã trốn khỏi phòng thí nghiệm trong ngày thứ \(d\).

Ràng buộc

• \(1\le L\le20\).
• \(1\le Q\le1\,000\,000\).
• \(S\) có độ dài \(2^L\) và chỉ gồm các ký tự 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.
• Với mọi \(1\le d\le Q\), xâu \(T_d\) có độ dài \(L\) và chỉ gồm các ký tự 0, 1, ?.

Phân nhóm

1. (5 điểm) \(L\le10\) và \(Q\le1000\).
2. (7 điểm) \(L\le10\).
3. (10 điểm) \(L\le13\).
4. (53 điểm) \(Q\le50\,000\).
5. (25 điểm) Không có ràng buộc bổ sung.

Ví dụ

3 5
12345678
000
0??
1?0
?11
???

1
10
12
12
36

4 8
3141592653589793
0101
?01?
??1?
?0??
1?00
01?1
??10
????

9
18
38
30
14
15
20
80

Nguồn

JOI 2017/2018, vòng chung kết, bài Snake Escaping. Đề do Japanese Committee for the International Olympiad in Informatics công bố. Đề gốc tiếng Anh. Bản dịch tiếng Việt theo CC BY-SA 4.0.