Phòng nghiên cứu JOI chứa ~2^L~ con rắn độc đánh số từ ~0..2^{L-1}~, mỗi con rắn chia đều thành L đoạn, màu của mỗi đoạn là xanh hoặc đỏ. Con rắn thứ i được mã hoá bằng L bit, trong đó bit thứ ~k~ là ~1(c_k=1)~ nếu đoạn thứ ~i~ của nó màu xanh và bit thứ ~i~ bằng ~0 (c_k=0)~ trong trường hợp ngược lại. Đặt:

~i=∑_{k=1}^L c_k 2^{L-k} (0≤c_k≤1)~

Mỗi con rắn có một độ độc, là một số nguyên trong khoảng 0..9.

Các con rắn rất nhanh, chúng thường trốn khỏi phòng nghiên cứu JOI. Tuy nhiên vào cuối mỗi ngày chúng sẽ bị các nhân viên phòng thí nghiệm bắt lại. Những người dân sống gần phòng thí nghiệm do đã nhìn thấy rắn độc trốn thoát khỏi phòng thí nghiệm đã gửi khiếu nại. Có Q đơn khiếu nại, đơn thứ ~d(1≤d≤Q)~ mô tả về con rắn trốn khỏi phòng nghiên cứu trong ngày thứ ~d~ là một xâu ~T_d~ gồm L ký tự ~1/0/?~ tương ứng với màu xanh/đỏ/ không xác định trên L đoạn của con rắn.

Yêu cầu: với mỗi ngày, tính tổng độ độc của các con rắn có thể trốn khỏi phòng thí nghiệm.

Dữ liệu vào:

• Dòng đầu chứa hai số nguyên dương L,Q
• Dòng thứ hai chứa xâu S gồm ~2^L~ ký tự, trong đó '0' ~≤S[i]≤~ '9' cho biết độ độc của con rắn thứ ~i~.
• ~Q~ dòng sau, dòng thứ ~d+2~ chứa ~L~ ký tự liên tiếp là tương ứng đơn khiếu nại của những người dân sống quanh phòng nghiên cứu trong ngày thứ d.

Kết quả ra: Gồm Q dòng, dòng thứ d là tổng độ độc có thể của các con rắn trốn khỏi phòng nghiên cứu trong ngày thứ d.

Các giới hạn:

• ~1≤L≤20~
• ~1≤Q≤10^6~

Ví dụ:

INPUT

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

OUTPUT

1 
10 
12 
12 
36

Giải thích: L = 3, có ~2^3 = 8~ con rắn độc. Mỗi con được chia thành 3 phần. Có 5 đơn khiếu nại.

• Ngày đầu tiên, những con rắn độc có thể trốn thoát khỏi phòng thí nghiệm là duy nhất con rắn 0. Tổng các độc tính là 1.
• Ngày thứ hai, những con rắn độc có thể trốn thoát khỏi phòng thí nghiệm là 0, 1, 2, 3. Tổng độ độc là 10.
• Ngày thứ ba, những con rắn độc có thể trốn thoát khỏi phòng thí nghiệm là 4, 6. Tổng các độc tính là 12.
• Ngày thứ tư, những con rắn độc có thể trốn thoát khỏi phòng thí nghiệm là 3, 7. Tổng các độc tính là 12.
• Ngày thứ năm, những con rắn độc có thể trốn thoát khỏi phòng thí nghiệm là 0, 1, 2, 3, 4, 5, 6, 7. Tổng các độ độc là 36.