Phòng thí nghiệm NTDU có nuôi tổng cộng \(2^L\) con rắn độc. Các chú rắn này được đánh số \(0\), \(1\), \(2\),..., \(2^L-1\). Trên da của mỗi chú rắn có \(L\) đốt màu sắc, được ghi nhận theo thứ tự từ đầu đến đuôi, mỗi đốt sẽ mang màu xanh hoặc màu đỏ. Với chú rắn \(i\), đặt \(i=\sum_{k=1}^L c_k\cdot 2^{L-K}\) \((0\leq c_k\leq 1)\) là dạng biểu diễn nhị phân của \(i\), ta có thể thu được những thông tin sau:

• Nếu \(c_k=0\), đốt thứ \(k\) của chú rắn \(i\) sẽ có màu xanh.
• Nếu \(c_k=1\), đốt thứ \(k\) của chú rắn \(i\) sẽ có màu đỏ.

Ngoài ra, mỗi chú rắn cũng sẽ được đánh một nhãn từ \(0\) đến \(9\) thể hiện cường độ độc tố trong người nó. Một xâu \(S\) độ dài \(2^L\) gồm các ký tự chữ số từ \(0\) đến \(9\) sẽ được cho trước trong input để thể hiện cường độ độc tố của tất cả các chú rắn trong phòng thí nghiệm NTDU theo đúng thứ tự chỉ số.

Các chú rắn kể trên rất nhanh nhẹn và nghịch ngợm nên chúng thường xuyên trốn khỏi phòng thí nghiệm NTDU để la cà sang các khu dân cư lân cận. Phòng thí nghiệm NTDU đã nhận được tổng cộng \(Q\) lá thư phàn nàn trong \(Q\) ngày liên tục (mỗi ngày một lá thư) từ cư dân gần đó. Ở mỗi bức thư vào ngày thứ \(d\) \((1\leq d\leq Q)\), các cư dân đều ghi vào một xâu \(T_d\) độ dài \(L\), gồm các ký tự 0, 1, và ?, để thể hiện thông tin về các chú rắn mà họ bắt gặp được:

• Nếu ký tự thứ \(j\) \((1\leq j\leq L)\) của \(T_d\) là 0 thì đốt thứ \(j\) của tất cả các chú rắn trốn thoát vào ngày đó sẽ đều mang màu xanh.
• Nếu ký tự thứ \(j\) \((1\leq j\leq L)\) của \(T_d\) là 1 thì đốt thứ \(j\) của tất cả các chú rắn trốn thoát vào ngày đó sẽ đều mang màu đỏ.
• Nếu ký tự thứ \(j\) \((1\leq j\leq L)\) của \(T_d\) là ? thì cư dân không quan sát rõ được màu sắc đốt thứ \(j\) của các chú rắn trốn thoát.

Lưu ý rằng, vào cuối mỗi ngày thì các nhân viên phòng thí nghiệm NTDU đều sẽ bắt lại được tất cả những chú rắn đã trốn thoát trong ngày hôm đó, nên hoàn toàn có khả năng một chú rắn có thể sẽ trốn thoát vào hai ngày khác nhau và được ghi nhận lại màu sắc ở hai xâu trong input.

Với mỗi số nguyên \(d\) từ \(1\) đến \(Q\), bạn hãy lập trình tính tổng cường độ độc tố của tất cả các chú rắn có thể đã trốn thoát trong ngày \(d\) nhé.

Input

Dòng đầu chứa hai số nguyên dương \(L\) và \(Q\).

Dòng tiếp theo chứa xâu \(S\) độ dài \(2^L\) gồm các ký tự chữ số từ 0 đến 9.

Dòng thứ \(d\) \((1\leq d\leq Q)\) trong \(Q\) dòng tiếp theo chứa một xâu \(T_d\) gồm các ký tự 0, 1, hoặc ?.

Output

Ghi ra \(Q\) dòng, dòng thứ \(d\) chứa một số nguyên thể hiện tổng cường độ độc tố của tất cả các chú rắn có thể đã trốn thoát trong ngày thứ \(d\).

Ví dụ

Sample input 1

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

Sample output 1

1
10
12
12
36

Giải thích

Trong ví dụ trên, \(L=3\) nên phòng thí nghiệm NTDU sẽ có tổng cộng \(2^3=8\) chú rắn, mỗi chú rắn có \(3\) đốt màu sắc.

• Vào ngày thứ nhất, chỉ duy nhất một chú rắn \(1\) có thể đã trốn thoát, nên tổng cường độ độc tố là \(1\).
• Vào ngày thứ hai, các chú rắn có thể đã trốn thoát là \(0\), \(1\), \(2\), \(3\), tổng cường độ độc tố là \(10\).
• Vào ngày thứ ba, các chú rắn có thể đã trốn thoát là \(4\) và \(6\), tổng cường độ độc tố là \(12\).
• Vào ngày thứ tư, các chú rắn có thể đã trốn thoát là \(3\) và \(7\), tổng cường độ độc tố là \(12\).
• Vào ngày thứ năm, các chú rắn có thể đã trốn thoát là \(0\), \(1\), \(2\), \(3\), \(4\), \(5\), \(6\) và \(7\), tổng cường độ độc tố là \(36\).

Sample input 2

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

Sample output 2

9
18
38
30
14
15
20
80

Ràng buộc

Trong tất cả các test:

• \(1\leq L\leq 20\)
• \(1\leq Q\leq 10^6\)

Subtasks

• Subtask 1 (5 điểm): \(L\leq 10\), \(Q\leq 1000\).
• Subtask 2 (7 điểm): \(L\leq 10\).
• Subtask 3 (10 điểm): \(L\leq 13\).
• Subtask 4 (53 điểm): \(Q\leq 5\cdot 10^4\).
• Subtask 5 (25 điểm): Không có ràng buộc gì thêm.